phpmyadmin, "Error establishing a database connection&a

Both a friend and I signed up for linode this week with near identical VPS packages, both running Ubuntu 64 bit. We did a standard roll out on each with apache, mysql, php, phpadmin, etc. The odd thing is that on my vps I cannot connect to phpmyadmin via console or http. If I connect via http, I am greeted with the pleasant, "Error establishing a database connection". I have checked and rechecked all of the config files. If you try connecting via console (and perhaps this is not the correct way to troubleshoot this) you get the following:

root@freyja:/# wget localhost/phpmyadmin
--2010-07-17 20:34:41--  http://localhost/phpmyadmin
Resolving localhost... 127.0.0.1
Connecting to localhost|127.0.0.1|:80... connected.
HTTP request sent, awaiting response... 404 Not Found
2010-07-17 20:34:41 ERROR 404: Not Found.

I have uninstalled and reinstalled both mysql and phpmyadmin. What am I missing here?

Thanks!