To see the problem, start from "emacs -Q":

   M-x
   M-r      ;; Emacs prompts "Previous element matching regexp:"
   C-g

   M-- M-r  ;; Emacs prompts "Previous element matching regexp:" (?!)

In the last line, the prefix argument is negative, so the search will 
actually be for the *next* matching element. The attached patch fixes 
this so that the prompt message accounts for the prefix arg.

While I was here, I also made 'next-matching-history-element' use 
'format-prompt' like its 'previous-...' sibling.