I'm not sure if they're turing complete, however many many many common regexp dialects (as seen in perl, ruby, python, etc.) are more powerful than what you learned as "regular expressions" in CS class, they're at least as powerful as a PDA.
PCREs (ie, the regular expressions that Perl uses) are NP-hard, since they allow backreferences.
reference: http://cstheory.stackexchange.com/questions/1047/where-do-mo...