You guys utterly, amazingly, supremely ROCK!
I'm a DreamHost user and have been plagued with this very same problem, which has stumped me for a couple of weeks, because connecting to the database from the shell worked out perfectly. I was (erroneously) assuming that some plugin was malfunctioning under PHP 5.4, and thus the strange database connection error.
I should have immediately noticed that this error only appears on very old websites, where the database password hasn't changed in several years... but somehow I missed the 'connection' (pun intended). I just thought it was a bad plugin somewhere.
DreamHost's control panel, like 1and1's or Bluehost's, allows the database password to be changed easily, and after that's done, the sites work flawlessly under PHP 5.4.
Woo hoo! Kudos to @ffreundt for getting us a working solution!