SEF in Joomla 1.5 RC2 is completely broken. Don't use it.
Check our Front-page article and discussion thread about Joomla 1.5 RC2...as well as the forum we point to in that thread.
You may try 1.5 nightly or SVN but i can't tell if it's yet fixed.
Or just stick to Joomla 1.0 for now.