I solved this as I was typing the support request here, so I thought I'd share it...

I created a db for a separate application running on the same server as my elgg installation. Absent-mindedly, the user I created was the same name as the user associated with the hostname_elgg db. This elicited the error "Elgg couldn't connect to the database using the given credentials."

I deleted it the new db, but still got the error. I created another db with the same offending user name but this time also the same password as that associated with the hostname_elgg db. After that, my website was magically restored! I then deleted the new db.