I bet the Service account is the account used to install Exchange server? Did you change this password too?
>>"Username: Service"
Is Exchange server on the machine that the message appears.
I have seen this problem that some exchange services fail to start after changing the Service account password.
Unfortunately I don't know the fix (I just changed mine back after an exasperating effort to fix it). If someone else knows....
AsusA7N8X, AthlonXP2200
gForce4600+ti & Audigy Platnium, FPS SOUND. AKA- The ultimate gaming machine (well it WAS three years ago anyway).