Ok let me give you the lowdown:
I'm running MySQL 4.0.20a-nt on a Windows XP Pro Box. Install went fine. I set a password for root using: "mysqladmin -u root password 'mypasshere'" This *seemed* to work. I then try: "mysql -u root -p "mypasshere" and/or "mysql -u root -p" This returns: "ERROR 1045: Access denied for user: 'root@localhost' (Using Password NO). I also try: "mysqladmin -h localhost -u root -p "mypasshere" this produces a password prompt - I input the correct password and I get: "MYSQLADMIN: connect to server at 'localhost' failed error: 'Access denied for user: 'root@localhost' (Using Password: YES). I can login using: "mysql" and it works fine - no password required. I also edited my.ini using WinMySQLAdmin to read:
__________________________________________________ _______________
#This File was made using the WinMySQLAdmin 1.4 Tool
#7/2/2004 4:06:57 PM

#Uncomment or Add only the keys that you know how works.
#Read the MySQL Manual for instructions

[mysqld]
basedir=e:/mysql
#bind-address=192.168.0.2
datadir=e:/mysql/data
#language=e:/mysql/share/your language directory
#slow query log#=
#tmpdir#=
#port=3306
#set-variable=key_buffer=16M
[WinMySQLadmin]
Server=E:/mysql/bin/mysqld-nt.exe
user=root
password=oldtimer
QueryInterval=10
__________________________________________________ _______________

I'm not sure what the problem is here, but I cannot add users or access the database using root. There is one database in the server by default, the "test" database.
Any help appreciated!

Have you tried the following syntax:
shell> mysql --user=root --password=mypasshere test

where 'test' is the name of the database you wish to logon to on localhost.