Do seu comando acima, parece haver uma incompatibilidade de PQ - QP na ortografia, isso é apenas um erro de digitação?
É o caso que o Apt está definido para sempre preferir lúcido? (Não aparece como tal da saída do apt-cache embora ...) Faz:
apt-get -t mycompany-staging install {python-ampqlib,python-amqplib}
faz alguma diferença?