I made the incorrect assumption that the md5-encrypted passwords stored in the database were, for whatever reason, incompatible between the old version of Redhat Linux/PHP and the new version of SuSE 9.1/PHP 4.3.4. That is, of course, not true.
Actually, the problem is that the "intranet" PHP application I'm migrating from the old server to the new server makes use of session variables ... in a way that's incompatible with the default settings in PHP 4.3.4.
The solution was simply to modify /etc/php.ini:
register_globals = "On";
If you're curious, you can read more about the issue here:
http://us4.php.net/register_globals