Problem w/ Adding MySQL Users

I am having some problems with the PMA 'Privileges' Feature. Whenever I create a user with a password, and then try to log in using that user or log into MySQL through command line with that user, I get 'access denied' errors. However, if I create a user without a password, it works fine. How can I fix this problem with the passwords?

I heard that the password format changed between MySQL 4.0.18 (which I am using now) and MySQL 4.1.1 (which I was using before). I did a clean install of 4.0.18 and didn't restore the 'mysql' database from 4.1.1 when reverting back to 4.0.18

Any idea why users with passwords doesn't work?