Right, that makes sense. Then you need the expression to match the first character in the way you were doing before.
One way to solve the problem is to use:
regex: ^([a-Z])
replace: _$$1
This means: match the first character, replace with "_" concatenated with the character that was matched.
Depending on the regex engine, the "(" can also be "\(", and the "$$1" can be "$1" or "\1". (yep, it's annoying that not everybody follows the same syntaxes).