MySQL not close cleanly

Hello, I've been having some troubles my mysql. My current system is on a debian squeeze running LAMP. This is the error I'm getting when I restart the mysql server,

Stopping MySQL database server: mysqld.
Starting MySQL database server: mysqld ..
Checking for tables which need an upgrade, are corrupt or were
not closed cleanly..

I restarted it because I was having some difficulties logging into the database.

Is there a fix for this?

PS. I've already tried the check, optimize, and repair, as well as removing the mysql server completely and installing it back again-still no luck.