Did you try this:
Code:
Title</p><p class="calibre1">\s*Page\s*[0-9]+\s*of\s*[0-9]+
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.
Edit:
Note if non-breaking spaces are your problem you can create a character class to include them. Instead of \s*, use this: [\su00a0]*