I have this very same problem.
www.joomlapolis.com/forum/147-potential-bug/167846-underscore-in-username-err-when-accesprofile-page#167846
I enabled SEF to allow users to distribute their user profiles using their username like this:
/index.php/ms-profile/userprofile/username
However if the username has an underscore in it like "john_smith", and the above url is used, I get a page saying "This profile does not exist or is no longer available".
Ok, so how can I fix this. Or, can I restrict the username creation to have no underscores? Maybe through the username field? Are there any other known characters that are allowed in the username that cause this problem?
I only have like a few users with underscore in their name, so I can manage otherwise. But I don't want to have more created. What should I do?