Our DMS Software Reengineering Toolkit can likely implement your solution pretty well. It is designed to carry out reliable source code transformations, by using AST to AST transforms coded in surface-syntax terms.
It has a PHP Front End which is a full, precise PHP parser, AST builder, and AST to PHP-code regenerator. DMS provides for AST prettyprinting, or fidelity printing ("preserve column numbers where possible").
This combination has been used to implement a variety of trustworthy PHP source code manipulation tools for PHP 4 and 5.
EDIT (in response to a somewhat disbelieving comment):
For the OP's solution, the following DMS transformation rule should do most of the work:
rule replace_underscored_identifier_with_namespace_path(namespace_path:N)
:namespace_path->namespace_path
"\N" -> "\complex_namespace_path\(\N\)"
if N=="NCLASS_OR_NAMESPACE_IDENTIFIER" && has_underscores(N);
This rule finds all "simple" identifiers that are used where namespace paths are allowed,
and replaces those simple identifiers with the corresponding namespace path constructed
by tearing the string for the identifier apart into consitutent elements separated by underscores. One has to code some procedural help
in DMS's implementation langauge, PARLANSE, to check that the identifier contains underscores ("has_underscores"), and to implement the tear apart logic by building the corresponding namespace path subtree ("complex_namespace_path").
The rule works by abstractly identifying trees that correspond to language nonterminals (in this case, "namespace_path", and replacing simple ones by more complex trees that represent the full name space path. The rule is written as text, but the rule itself is parsed by DMS to construct the trees it needs to match PHP trees.
DMS rule application logic can trivially apply this rule everywhere throughout the AST produced by the PHP parser.
This answer may seem overly simple in the face of all the complicated stuff that makes up the PHP langauge, but all that other complexity is hidden in the PHP langauge definition used by DMS; that definition is some 10,000 lines of lexical and grammar definitions, but is already tested and working. All the DMS machinery, and these 10K lines, are indications of why simple regexes can't do the job reliably. (It is surprising how much machinery it takes to get this right; I've been working on DMS since 1995).
If you want to see all the machinery that makes up how DMS defines/manipulates a language, you can see a nice simple example.