Are you referring to the SDE user password, or to the data owner account password(s)?
By what do you mean "service"? Application Server or ArcGIS Server?
I never create services using the data owner account -- best practice calls for a
different user with the least possible permission (ideally, just SELECT), granted
through roles -- but the problem is the same:
You can't change the password of the service user without impacting services.
You must stop (or delete) all impacted services, and alter the connection (or
recreate them entirely). This is another reason to use extremely limited user
accounts for services -- If they have nothing beyond query ability, there's less
reason to change the browse user's password.