baschuve --
Really good question.
As SPLM, we've actively resisted providing a utility for this, because there are some pretty nasty side effects if the end user doesn't approach this perfectly.
The biggest opportunity for nasty problems here is interpart expressions. Interpart expressions (IPEs) are a pretty simple "pull" or "reference" relationship, where the "referencing" or "destination" part retains a reference to the "source" or "target" part, but not the other way around. As such, it's difficult to predict where expressions are being referenced unless all of the potential downstream referencing parts are open in the NX session. (And yes, if the referencing parts are open in the session, then we can very easily tell you whether an expression is being referenced or not.)
But it's pretty easy to get into a situation where you've got a source part open, with one (or some, or all) of the downstream parts containing IPEs that reference expressions in that source part NOT currently open. And in that situation, if you rename expressions in the source part, the downstream referencing parts will not know about that change.
And so the next time you open those downstream referencing parts, the IPEs there will still be looking for the old expression names.
...which may no longer be there, in which case the IPEs will be put into a "broken" state in NX 10+ (the last known good value cached, waiting to be directed to a new parent) or converted to a constant value (with the interpart reference deleted entirely) in versions prior to NX 10.
Or even worse, if you've started with a situation like this:
p1 <-- With an IPE "source":

1 referencing this one
p2
p6 <-- With an IPE "source":

6 referencing this one
p10 <-- With an IPE "source":

10 referencing this one
p11
p23
p24
p25
p34
p68 <-- With an IPE "source":

68 referencing this one
p74
...and you renumber the expressions without the downstream part open, then you would end up with:
p1 --> p1 <-- With an IPE "source":

1 CORRECTLY still referencing this one
p2 --> p2
p6 --> p3
p10 --> p4
p11 --> p5
p23 --> p6 <-- With an IPE "source":

6 referencing
THE WRONG VALUE
p24 --> p7
p25 --> p8
p34 --> p9
p68 --> p10 <-- With an IPE "source":

10 referencing
THE WRONG VALUE
p74 --> p11
?? <-- With an IPE "source":

68 now
BROKEN
...which is all kinds of wrong. :-/
...and which would require some manual re-association of the broken IPEs to fix.
Presuming you remembered how all of the IPEs were hooked up before.
For all of the referencing parts.
[NOTE: One important lesson here is that giving important expressions a meaningful name is a really good idea.]
And so in the end we're SO wary of creating this problem in our customers' assemblies that we've actively chosen NOT to provide a utility to renumber expressions.
And so if you choose to pursue this with automation anyway, beware... There be monsters. ;-)
Does that make sense?
Taylor Anderson
NX Product Manager, Knowledge Reuse and NX Design
Product Engineering Software
Siemens Product Lifecycle Management Software Inc.
(Phoenix, Arizona)