Character encodings are a little changeling, it could be that your data (which, after all is all just binary).
You should first check your database's encoding, and the table's individual encoding. The encoding referrs to the internal storage… a good example might be that you're storing ISO-8859-1 so the database expects only ISO-8859-1, but if some of the data is in Hebrew, these characters aren't valid in ISO-8859-1.. but if the clients putting the data in, and getting it out are using ISO-8859-8 (Hebrew), it will mostly appear to work.
Here is a guide from MySQL on the topic.
I would recommend (where possible) that you use UTF-8, there's a number of reasons, but please, please do not blindly alter your databases encoding, as this doesn't re-encode the data, but simply informs MySQL that it should be treated like UTF8. (Which will corrupt your data, if the source is ISO-8859-1 or ISO-8859-8. here is another a primer on character encodings, and you'd be well served to give it the once over. "The bare minimum any software engineer should know about Unicode"
Further to that, your terminal (your bash session), terminal emulator (putty) and db console (mysql) all have to know what encoding they are dealing with… it's best to tell them UTF-8… and then work with UTF-8 data.