2nd Comput fail in "networking stage" when launching new instance

I already have a working setup on one machine which runs all services.
I'm trying to setup a 2nd machine which only runs compute, but it fails on the "networking stage" of launching an instance.

Error is "RPC Timeout". Can someone with a better understanding of how everything communicates help me figuring out what the problem is?

Controller logs (1st machine which already can run instances without problems): https://dl.dropbox.com/u/2468164/controller.logs
Failing compute log (new machine that should hook up to the 1st): https://dl.dropbox.com/u/2468164/compute.log

I've ran custom python script to simply try the connectivity of rabbitmq from one server to the other, this works fine.
Nova client command works fine.
Mysql client works fine.

nova-manage service list shows all happy smileys.

I don't know how to further investigate this problem