Acabo de probar lo mismo que haces. Cree un proyecto Audio-CD en nero Burning ROM. Arrastre un par de canciones MP3 en letras cirilicas, y estas se mantenian, pero despues de grabar los nombres se cambian por Track01.cda y asi sucesivamente. Probe con Roxio Easy CD Creator, pero lo mismo.
Yo de esto no se mucho, pero por lo menos no me salio en ninguno de los 2 programas el problema que a ti.
Te recomiendo probar con una version que soporte letras cirilicas. Si tienes la version en español de Windows, entonces instala el idioma correspondiente en el Panel de Control, Idiomas o Estandares regionales (no se como sera en español

).
Bueno, por ahora no se ocurre nada mas. Si logras hacerlo, cuentanos.