Well I also had this problem and it took me a while to figure it out.
Basically what you need to do is enter your SQL Database, and edit wp_fb_albums table. Manually change the collation of the rows from latin1_swedish_ci to UTF8 (i use utf8_general).
The actual rows you need to change are: Name, Description and Location.
After you do that, you may update your albums.
Hope that helps,
R. Landau
