Yes, impossible to look for "marina and the diamonds" for example, either in the search bar or in the new Ubuntu Music Store. I can understand that the problem can be hard to fix though it is only one radiobox to check by default in the layout options (see answer 41 by Christophe Mehay)... But really no one can say that not being able to write spaces in a search box is a huge usabilty issue. Just imagine what a (French) newcomer to Ubuntu would think!
And by the way I don't know what those unbreakable spaces are for, I have never noticed them so I don't think anyone would miss them.
Another simple fix is to use Banshee. I ran into this issue on my Lucid netbook when I wanted to check the new Music Store and to see how Rhythmbox had evolved, I am more than disappointed and it is not even Rhythmbox fault, what a shame.