This is the guide that i use (hence why I threw it on the forum ;)). I would totally recommend only using hosts with CLI access as it makes certain tasks much easier (backing up with tar, utilizing the mysqldump command, etc).
That error occours becasue you're reaching your space limit (see
Disk limit reached), you can't write after you reach your limit.
Most hosts "secure" the mysql server by not allowing external (off site) connections, otherwise i'd tell you to use sqlyog (as i believe it will allow you to dump all data to your local machine). The backup utility in the forum will also reach this space limit, so no use recommending that... You may contact your host, and ask if they could dump the sql database for you as you reach this limit, a lot of them will actually be helpful for "backups".
As for recommending a host, I only really recommend VPS for larger sites, and in that I recommend
www.webintellects.com