Acabei de descobrir que desativar o uso de um proxy da web parecia corrigir isso para mim. Minhas configurações de proxy do IE foram configuradas automaticamente no meu domínio inicial (para usar o Privoxy para navegação). Quando desativei a configuração automática, todos os aplicativos e atualizações na minha fila do Store foram instalados como deveriam.
Agora, só preciso descobrir como continuar usando o Privoxy e, ao mesmo tempo, garantir que o BITS / Store continue funcionando.