Mysql 4.1.x usa otro tipo de contraseñas para los usuarios de este .. De hecho .. si te fijas BIEN en el tutorial que seguistes .. se habla de Mysql 4.0.x no de Mysql 4.1.x .. las versiones son muyyyyyyyyyy importantes que se respeten si sigues una guía de instalación. Lo que la guía explica y "afirma" es sólo para las versiones que ahí se mencionen de todo lo que indican.
Realmente no sé como usar dichas "nuevas contraseñas" .. pero si que sé que puedes usar el método antigüo de control de contraseñas de versiones inferiores de Mysql.
Lee este mensaje:
http://www.forosdelweb.com/f18/valores-blanco-insert-php-248175/
Un saludo,