I believe I have fixed this. I modified three lines in comprofiler.html.php, #170, #1114 and #1213. Originally:
[code:1] var r = new RegExp("^[a-zA-Z](([\.\-a-zA-Z0-9@])?[a-zA-Z0-9]*)*$", "i"«»);[/code:1]
Now:
[code:1] var r = new RegExp("^[a-zA-Z0-9](([\.\-a-zA-Z0-9@])?[a-zA-Z0-9]*)*$", "i"«»);[/code:1]
I don't know which line is the magic bullet, but from the looks of it #1213 is for forgotten username. This may likely be an ugly hack, but it seems to work for me in very limited testing. The user is created with the password that previously caused problems. The user is able to login properly as well.
I didn't state this previously, but this was also present in the 1.5 RC3 download from the joomla main page.