Having very similar symptom as bug 637659. In this case, however, I have two clusters in different locations connected over openvpn. I am using the latest UEC image release (release-20100827).
It starts and runs fine on cluster1 (which is in the same location as the CLC). I can connect via ssh on cluster1.
But fails on cluster2 (which has two servers: one is a CC-SC connected via openvpn to the CLC, and an NC, which is not running openvpn, but uses the CC as its default route out so it can talk to Walrus over the tunnel).
The instance does start up on cluster2. Using euca-get-console-output it eventually hangs up with:
cloud-init running: Tue, 14 Sep 2010 14:57:54 +0000. up 9.23 seconds
waiting for metadata service at http://169.254.169.254/2009-04-04/meta-data/instance-id
14:57:54 [ 1/100]: http error [500]
14:57:56 [ 2/100]: http error [500]
14:57:57 [ 3/100]: http error [500]
[...snip...]
Using a different image I can confirm that the networking seems good. When an instance starts up on the remote cluster (cluster2) you can ping it and ssh into it. But the metadata service still returns a 500 error.