To add to the previous, the tracebacks don't even indicate where the problematic string is, so you have to be good at guessing, or just have the patience to hunt it down (a somewhat daunting task with 18398 files in the collection).

There is no user-visible error when started from the Gnome menu, just a steady firehose of errors to .xsession-errors.  As a minimal workaround of sorts, there should be a dialog box saying there is a problem, if this cannot be fixed easily.

Here are some excerpts from .xsession-errors:

-----------------------
 run ( /usr/share/exaile/xl/library.py @ 682):
-----------------------
Traceback (most recent call last):
  File "/usr/share/exaile/xl/library.py", line 720, in run
    self.do_function(loc)
  File "/usr/share/exaile/xl/library.py", line 764, in do_function
    tr = read_track_from_db(db, unicode(loc, xlmisc.get_default_encoding()))
  File "/usr/lib/python2.5/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 57-59: invalid data

-----------------------
 run ( /usr/share/exaile/xl/library.py @ 682):
-----------------------
Traceback (most recent call last):
  File "/usr/share/exaile/xl/library.py", line 720, in run
    self.do_function(loc)
  File "/usr/share/exaile/xl/library.py", line 764, in do_function
    tr = read_track_from_db(db, unicode(loc, xlmisc.get_default_encoding()))
  File "/usr/lib/python2.5/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 57-59: invalid data

-----------------------
 run ( /usr/share/exaile/xl/library.py @ 682):
-----------------------
Traceback (most recent call last):
  File "/usr/share/exaile/xl/library.py", line 720, in run
    self.do_function(loc)
  File "/usr/share/exaile/xl/library.py", line 764, in do_function
    tr = read_track_from_db(db, unicode(loc, xlmisc.get_default_encoding()))
  File "/usr/lib/python2.5/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 57-59: invalid data

-----------------------
 run ( /usr/share/exaile/xl/library.py @ 682):
-----------------------
Traceback (most recent call last):
  File "/usr/share/exaile/xl/library.py", line 720, in run
    self.do_function(loc)
  File "/usr/share/exaile/xl/library.py", line 764, in do_function
    tr = read_track_from_db(db, unicode(loc, xlmisc.get_default_encoding()))
  File "/usr/lib/python2.5/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 57-59: invalid data

-----------------------
 run ( /usr/share/exaile/xl/library.py @ 682):
-----------------------
Traceback (most recent call last):
  File "/usr/share/exaile/xl/library.py", line 720, in run
    self.do_function(loc)
  File "/usr/share/exaile/xl/library.py", line 764, in do_function
    tr = read_track_from_db(db, unicode(loc, xlmisc.get_default_encoding()))
  File "/usr/lib/python2.5/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode bytes in position 57-59: invalid data

(etc etc)