I'm sorry, I didn't see that you checked old_passwords until after I hit Enter.
Summary:
1. When you use PASSWORD(), it generates a 41-character hash.
2. Server rejects this, saying that it needs a 16-character password hash.
3. old_passwords=0.
In this case, I'd say your grant tables are using old definitions and need to be updated. Check with
SHOW CREATE TABLE mysql.user\G as I suggested previously and see what length is specified for the Password column. If it's not CHAR(41), then that's your problem, and you need to upgrade the grant tables.
Jon Stephens
MySQL Documentation Team @ Oracle
MySQL Dev Zone
MySQL Server Documentation
Oracle