So... Your method is close, but due to the way JavaScript's replace function works, it will only replace the first open and first close pair. Since there is no instance of open/close after the first close, the replace method stops there. Here's how the search method is thinking:
[quote]Quote by: user1 [quote]Quote by: user2 ads[/quote]Test[/quote]Testing 2.
^ Found open, look for close.....................^ Found! Look for open........
Since there's no open after the close, it stops there and executes the replace:
[quote]Quote by: user1 [quote]Quote by: user2 ads[/quote]
becomes:
<div class='quote'>Quote by: user1 [quote]Quote by: user2 ads</div>
and now the whole string reads:
<div class='quote'>Quote by: user1 [quote]Quote by: user2 ads</div>Test[/quote]Testing 2.
This mis-matched pair of tags is what you are seeing, and it displays funny. But if you execute the same replacement again, the opening of the first replacement will match the closing of the second, and vice versa. Odd, but it does however ensure that the HTML has one open tag for each end tag, even if the input does not, which is a surprising, yet desirable outcome. To continue the example:
<div class='quote'>Quote by: user1 [quote]Quote by: user2 ads</div>Test[/quote]Testing 2.
^ Found Open, look for close........^ Found! .........
And now replace:
[quote]Quote by: user2 ads</div>Test[/quote]
with
<div class='quote'>Quote by: user2 ads</div>Test</div>
to get the whole string:
<div class='quote'>Quote by: user1 <div class='quote'>Quote by: user2 ads</div>Test</div>Testing 2.
Which is exactly what you wanted, although it is an odd and slightly hacky method, but yet HTML safer than some other methods you could be using.
I wrote a simple change to your jsfiddle that simply repeats the replacement until back-to-back replacements result in the same string: http://jsfiddle.net/gRaFW/6/
Note that this method should work for nested tags, as well as back-to-back tags. If the tags are mis-matched, this will break, and nothing but more complex logic, or a library will help. This will produce 2 tags, one open and one close, but there's no guarantee those tags match each other, eg:
[b][quote]Broke[/b][/quote]
So be careful