For your situation, I'd suggest trying to following for each bad column (connected over a utf8 connection):
// create a new column to store the latin1
alter table <table> add <column-latin1> <length> character set latin1;
// copy the utf8 data into the latin1 column without charset conversion
update <table> set <column-latin1> = binary <column-utf8>;
// verify the latin1 data looks OK
select <column-latin1> from <table>;
// copy the latin1 column into the utf8 column WITH charset conversion
update <table> set <column-utf8> = <column-latin1>;
// verify the new, properly encoded UTF8 data looks OK
select <column-latin1> from <table>;
// remove the temporary columns
alter <table> drop <column-latin1>;
And set your clients to use a UTF8 connection.