I fixed this problem in this changeset (http://hg.savannah.gnu.org/hgweb/octave/rev/9db32cabeacf). You will need to build from Mercurial sources with a version greater than or equal to 15541:9db32cabeacf in order to see the fix.

On my local machine, with my patch applied, your latest test runs fine so I think the single patch will fix both problems.

Thanks for the update Rik. If it helps, I can do some tests if you give me a patch.
Perhaps totally unrelated, but I noticed another problem with regexp:
MATLAB returns
as expected, while Octave returns empty fields.

This small little behavior has exposed some real problems in the regexprep code. I've had to rewrite a large amount of C++ code. I've got a solution that works now, but I want to run some of it by the octavemaintainers list before committing the changes.

Thanks for looking into this.
With MATLAB R2012a, I get:

Okay, I've done some digging and Octave is not quite handling things correctly. Can you run a few tests on Matlab to see how they interpret things?

I'm going to reopen this issue. From your testing, it appears that Octave is interpreting escape character sequences twice which is not correct. I am going to change the Item Group to "Matlab Compatibility" since that is what is really being chased here.
What I think is going on is the following:
I am building a debug version of Octave and will check this out with gdb.

Thanks for your comments.
With MATLAB R2012a, I get this:
Let me know if you need other user cases.
I came across this with some MATLAB code I use to escape a string for insertion in LaTeX:
I am not sure how to write some code that will work similarly for both Octave and MATLAB.

I added some extra documentation about this in this changeset (http://hg.savannah.gnu.org/hgweb/octave/rev/8593bed236f1). Hopefully this helps with understanding why we have to do this now.

This is the new behavior of regexp and regexprep in order to be Matlabcompatible. Quoting from the NEWS file which lists significant changes from the last revision:
So, patterns like '\\' really look like "\\" which collapses to just "\" and this causes the problem. It would be useful, if you have access to Matlab, to verify that they haven't done a special case for '\\'. I rather doubt it though.
Either add an extra backslash when using escape sequences like "\n" or look at the regexptranslate function for another option.

Using the backslash escape character returns an error in regexprep and Octave dev with this call:
while it does not return the correct answer here:
It is fine with Octave 3.6.2.
