Unfortunately, those two fixes you posted haven't solved the problems we're experiencing.
I've created a very basic version of our setup which recreates the issues at hand: http://cl.ly/1e3X3P3R1O2o
In the file you'll see a very basic role (base), environment (tester) and cookbooks (apt, rabbitmq, postgres and other dependancies). With the cookbooks, Apt and RabbitMQ are using the patched versions you mentioned in the StackOverflow response. The PostgreSQL is the one on the community website.
Both the RabbitMQ and Postgres cookbooks are failing for the same reason: the APT cookbook isn't updating.
I'm running these recipes through Hosted Chef, on a Vagrant VM running Ubuntu 12.04 64bit.
Thanks in advance for your help, Az.