Did you try this:
Is it showing up correctly as matching in the regex wizard, but not act removing it during conversion? Usually when this happens it's one of two things - there are also non-breaking spaces hiding amongst the real spaces, or there is a bug/limitation where Calibre is showing you html in the wizard that's not exactly the same as the html that is provided to the Search and Replace feature during conversion.
Note if non-breaking spaces are your problem you can create a character class to include them. Instead of \s*, use this: [\su00a0]*