Failed to connect from slave to master with error "error connecting to master (1045)"
Eventually, I find the reason. The password is too long. I try to use a short password, and it works. I think mysql command may truncate the password if it is too long, but it appears the replication didn't do that for you.
I was getting the same error while I was setting replication after reinstalling mysql.
It got resolved by changing from IP to hostname as the Master_Host, though I am not sure if that was the cause as IP was being used previously and working fine.