I'm not a Debian man (we run FreeBSD), but a good place to start is to make a phpinfo file in the same directory and in the same virtual host as the eZ publish installation. Those the phpinfo find any Mysql client ?
Best regards
Egil Fujikawa Nes
WebDeal AS http://www.webdeal.no