I may have spoken too soon. As a test, I disabled all messaging settings, then did a soft reset of my iPhone 4. Once it rebooted, I went back in and enabled all the messaging settings, including Character count.
Now, if I open messaging and start a new message, and pick a phone number as send to (someone who I know does not have an Apple iOS 5 device), I do have character count back.
I just thought it should work, since iMessage already knows, as soon as a recipient is picked, whether it can send as iMessage or must use SMS or MMS, in which case why should those options not work as before. Since the reset fixed it, I can only assume some setting did not get set correctly when I first set up iOS 5 after the update.