My guess is that the MySQL host had not yet appeared to DNS. This often happens with one-clicks that create a new database host; the install takes place faster than DNS can be updated.
The fix is really easy ... just wait a bit (often less than an hour - sometimes only 10-15 minutes) and try the "finishing" install steps again (don't re-do the "one-click", just the emailed instructions).
One easy way to tell if the MySQL database host is "ready to rock" is to just browse to it in a browser. If DNS is updated and it can be reached, you will be presented with an apache authentication screen (and if you enter your db user/pass, you will be able to operate phpMyAdmin on that host).