I restarted all of the services on all of the machines, but nova-network fails to get to a happy state. I ran tail on the log, but it seems the process is in some type of loop and is spewing a ton of stuff into the log. Here is a paste of the primary error block that keeps appearing in the log:

http://paste.openstack.org/show/1536/

Thanks, Graham

With help from #openstack I found a solution. Problem seemed to be with old instance data in the DB. Nova-network appears to have been trying to resurrect the network for these instances (bug), but clearly was failing at this. I emptied the instances table and ran nova-manage project scrub and instances now start up and get a private address.

Thanks, Graham