Thanks for the speedy response. 

KDE v 3.5.2
K3b 0.12.14

The character you presume is correct (I can't type it.) The disk is a data DVD.

I fixed some of the filenames in konqueror, and will do the rest. However, here's the debugging output from k3b:

2291381
INFO: UTF-8 character encoding detected by locale settings.
 Assuming UTF-8 encoded filenames on source filesystem,
 use -input-charset to override.
Using VINCENT_DE_MOOR___BETWEE000.MP3;1 for  /Vincent De Moor - Between Two Fires.mp3 (Vincent De Moor - Between Two Fires (Armin van Buuren´s Ris.mp3)
Using THE_ORB___LITTLE_FLUFFY_000.MP3;1 for  /The Orb - Little Fluffy Clouds.mp3 (The Orb - Little Fluffy Clouds (Dance Mix).mp3)
Using SYSTEM_F___OUT_OF_THE_BL000.MP3;1 for  /System F - Out of The Blue (Paul Van Dyk remix).mp3 (System F - Out Of The Blue (Original 12'' Version).mp3)
Using SYSTEM_F___OUT_OF_THE_BL001.MP3;1 for  /System F - Out Of The Blue (Original 12'' Version).mp3 (System F - Out of the Blue (Extd).mp3)
Using SHPONGLE___DIVINE_MOMENT000.MP3;1 for  /Shpongle - Divine Moments Of Truth (Instrumental Remix).mp3 (Shpongle - Divine Moments Of Truth (Demented Rmx).mp3)
Using SAFRI_DUO___PLAYED_A_LIV000.MP3;1 for  /Safri Duo - Played A Live (DJ Tandu Rmx).mp3 (Safri Duo - Played-a-Live (Airscape Remix).mp3)
Using PRANA___SCARAB__SNAKE_TH000.MP3;1 for  /Prana - Scarab (Snake Thing Rmx).mp3 (Prana - scarab (snake thing remix).mp3)
Using LOST_TRIBE___GAMEMASTER_000.MP3;1 for  /Lost Tribe - Gamemaster (Signum Remix).mp3 (Lost Tribe - Gamemaster [Signum Mix].mp3)
Using GREEN_NUNS_OF_THE_REVOLU000.MP3;1 for  /Green Nuns Of The Revolution - Two Vindaloos & An Onion Bhag.mp3 (Green Nuns of the Revolution - Rock Bitch.mp3)
Using GREEN_NUNS_OF_THE_REVOLU001.MP3;1 for  /Green Nuns of the Revolution - Rock Bitch.mp3 (Green Nuns of the Revolution - Ring of Fire.mp3)
Using GREEN_NUNS_OF_THE_REVOLU002.MP3;1 for  /Green Nuns of the Revolution - Ring of Fire.mp3 (Green Nuns of the Revolution - Octofunk.mp3)
Using GREEN_NUNS_OF_THE_REVOLU003.MP3;1 for  /Green Nuns of the Revolution - Octofunk.mp3 (Green Nuns of the Revolution - Cor [edit].mp3)
Using GREEN_NUNS_OF_THE_REVOLU004.MP3;1 for  /Green Nuns of the Revolution - Cor [edit].mp3 (Green Nuns of the Revolution - Atomic Armadillo.mp3)
Using DAFT_PUNK___ONE_MORE_TIM000.MP3;1 for  /Daft Punk - One More Time (White Label 2000).mp3 (Daft Punk - One More Time (Radio Edit).mp3)
Using DAFT_PUNK___ONE_MORE_TIM001.MP3;1 for  /Daft Punk - One More Time (Radio Edit).mp3 (Daft Punk - One More Time (Club Mix).mp3)
Using CHEMICAL_BROTHERS___OUT_000.MP3;1 for  /Chemical Brothers - Out of Control (Sasha club mix).mp3 (Chemical Brothers - Out Of Control.mp3)
Using CHEMICAL_BROTHERS___BOMB000.MP3;1 for  /Chemical Brothers - Bomb The Bass.mp3 (Chemical Brothers - Bomb The Bass (bug powder dust mix).mp3)
Using BBE___SEVEN_DAYS_AND_ONE000.MP3;1 for  /BBE - Seven Days And One Week.mp3 (BBE - Seven Days And One Week (99 mix).mp3)
Using ASTRAL_PROJECTION___MAHA000.MP3;1 for  /Astral Projection - Mahadeva (96 Remix).mp3 (Astral Projection - Mahadeva (2000 remix).mp3)
Using AGNELLI_AND_NELSON___EVE000.MP3;1 for  /Agnelli and Nelson - Everyday (Radio Mix).mp3 (Agnelli and Nelson - Everyday (Original_Mix).mp3)
Using 303_INFINITY___AUDIO_FAN000.MP3;1 for  /303 Infinity - Audio Fantasy (Tbo & Vega Mix).mp3 (303 Infinity - Audio Fantasy (12 inch Vynl).mp3)
Incorrectly encoded string (Vincent De Moor - Between Two Fires (Armin van Buuren´s Ris.mp3) encountered.
Possibly creating an invalid Joliet extension. Aborting.

In the main messages, it says "Encountered an incorrectly encoded filename ... " "This may be caused by a system update which changed the local character set." ...