This command line utility seems to do a pretty good job of splitting MP3s into individual files using a cue file
http://mp3splt.sourceforge.net/
On Fedora Core 2, it was easily compiled after first compiling libmad (it'll complain nicely with the URL from where to grab libmad).
On Mandrake 10.1 Community, an mp3splt package can be found using urpmi
Hope this helps
-- Tom