Why can't I now connect to my hosted mySQL Database?

I have a small website and it uses a mySQL Database. I have an administration client tool which I run on my PC and this connects to my database and allows me to administer it.

All of a sudden I cannot connect to the Database. It is as if host=localhost can connect but the option, which is presumably, host=% has stopped working.

I have tried connecting using more than one client tool and cannot connect. I can still connect to other hosted databases.

Is there anything else I can try before I start to badger my Hosting Company?