Hi,
I had the exact same problem with the same setup as the original poster (Debian, Apache Mysql (4.0.18) PHP (4.3.4)).
So, I tried installing phpBB to check it wasn’t a general php problem and the phpBB install complained that php-mysql module wasn’t setup for use with MySQL ver4.
I didn’t need to recompile, just a cheeky dpkg-reconfigure php4-mysql and a restart of apache did the trick for me.
Hope this helps someone.
Cheers,
Craig.