Yes, a multi-pass approach is required if the elements are nested. This can be accomplished in one of two ways; matching from the inside out or from the outside in. Here are two tested scripts with fully commented regexes which illustrate each technique:
1. Replace from the inside out:
<?php // test.php Rev:20121016_0900
$re = '% # Match innermost [b]...[/b] structure.
    \[b\]              # Literal start tag.
    (                  # $1: Element contents.
      # Use Friedls "Unrolling-the-Loop" technique:
      #   Begin: {normal* (special normal*)*} construct.
      [^[]*            # {normal*} Zero or more non-"[".
      (?:              # Begin {(special normal*)*}.
        \[             # {special} Tag open literal char,
        (?!/?b\])      # but only if NOT [b] or [/b].
        [^[]*          # More {normal*}.
      )*               # Finish {(special normal*)*}.
    )                  # $1: Element contents.
    \[/b\]             # Literal end tag.
    %x';
printf("Replace matching tags from the inside out:\n");
$text = file_get_contents('testdata.txt');
$i=0; // Keep track of iteration number.
printf("i[%d]=%s", $i++, $text);
while(preg_match($re, $text)){
    $text = preg_replace($re, '<strong>$1</strong>', $text);
    printf("i[%d]=%s", $i++, $text);
}
?>
Output:
'''
Replace matching tags from the inside out:
i[0]=Some text here... [b][b]Hello, [b]PHP![/b][/b][/b] ... [b]and here[/b]
i[1]=Some text here... [b][b]Hello, <strong>PHP!</strong>[/b][/b] ... <strong>and here</strong>
i[2]=Some text here... [b]<strong>Hello, <strong>PHP!</strong></strong>[/b] ... <strong>and here</strong>
i[3]=Some text here... <strong><strong>Hello, <strong>PHP!</strong></strong></strong> ... <strong>and here</strong>
'''
2. Replace from the outside in:
<?php // test.php Rev:20121016_0901
$re = '% # Match outermost [b]...[/b] structure.
    \[b\]              # Literal start tag.
    (                  # $1: Element contents.
      (?:              # Zero or more contents alternatives.
        [^[]*          # Either non-[b]...[/b] stuff...
        (?:            # Begin {(special normal*)*}.
          \[           # {special} Tag open literal char,
          (?!/?b\])    # but only if NOT [b] or [/b].
          [^[]*        # More {normal*}.
        )*             # Finish {(special normal*)*}.
      | (?R)           # Or a nested [b]...[/b] structure.
      )*               # Zero or more contents alternatives.
    )                  # $1: Element contents.
    \[/b\]             # Literal end tag.
    %x';
printf("Replace matching tags from the outside in:\n");
$text = file_get_contents('testdata.txt');
$i=0; // Keep track of iteration number.
printf("i[%d]=%s", $i++, $text);
while(preg_match($re, $text)){
    $text = preg_replace($re, '<strong>$1</strong>', $text);
    printf("i[%d]=%s", $i++, $text);
}
?>
Output:
'''
Replace matching tags from the outside in:
i[0]=Some text here... [b][b]Hello, [b]PHP![/b][/b][/b] ... [b]and here[/b]
i[1]=Some text here... <strong>[b]Hello, [b]PHP![/b][/b]</strong> ... <strong>and here</strong>
i[2]=Some text here... <strong><strong>Hello, [b]PHP![/b]</strong></strong> ... <strong>and here</strong>
i[3]=Some text here... <strong><strong>Hello, <strong>PHP!</strong></strong></strong> ... <strong>and here</strong>
'''
Note the (?R) recursive expression used in the second approach.