I'm pretty sure they're rejecting usage of an unofficial regex API. Nothing to get too excited about and I'm definitely sure they're not rejecting pcre, etc.
It's not an unofficial regex API, It is the libicucore a regex library that is available on the phone. It is even available from the xcode "Add Existing Frameworks" dialog.
As kemiller said, this is likely about Apple wanting developers to use iOS4's built-in support for regular expressions, which, by the way, gives you the answer to your submission's title. Please edit it accordingly.