I just took down the Ubuntu server I installed as a VM almost a year ago and installed a new one. When I originally loaded that server and put WordPress on it I had several problems getting it to work revolving around the mySQL user for the database. I had the same issues this time around, but didn't use the same solution as I did then. Back then I went back and installed PHPmyadmin, because I couldn't locate a solution without installing it, anywhere including here. I used it the one time during setup and then did nothing with it. This time I found the link I'm going to place in this post and managed to get things working without adding unneeded software.
BTW, he does make one mistake that he corrects at the end. When he assigns the database permissions to the wordpress user he does not type in localhost and select it on the Hosts line. As I said he corrects it at the end and following his directions worked like a charm for me.