I would have had the same problem on 3 Ubuntu machines (two x32 and one x64), if I did not first see:
http://uksysadmin.wordpress.com/2011/10 ... -solution/
That is, I noticed the problem on on x32 pc and then fixes the problem, and followed the simple instructions for the other two machines.
Regrettably, unless you can get into your machine from LISH or something like that, this may not help.
Basically:
mkdir /run /run/lock
rm -rf /var/run /var/lock
ln -s /run /var
ln -s /run/lock /var
reboot
On my Linode, I just tar'd /var/run and /var/lock, untar'd them in /run and /run/lock, and after the reboot I did the rm's and ln's.
P.S.
On my Linode, I did the above in addition to following the **new** instructions for 11.04 -> 11.10 on
http://library.linode.com/troubleshooti ... 10-oneiric