Try this:
var string = "Replace this[quote]Here is a message[/quote]\nReplace this\n\n[quote]Another message[/quote]\nReplace this as well";
string.replace(/(\[\/quote\]\s*|^)([^[]+?)(\s*\[quote|$)/g, "$1[b]$2[/b]$3");
///// And we get:
// [b]Replace this[/b][quote]Here is a message[/quote]
// [b]Replace this[/b]
//
// [quote]Another message[/quote]
// [b]Replace this as well[/b]
See the jsFiddle as well.