Yes, the color scheme profile options take effect upon restart.
Ensure "Java Look and Feel" is set to "oracle" value.
"Java Color Scheme" profile option needs to be changed and it doesn't need the APPS Services to be restarted. You need to close,logout and relogin to forms.
If the users are unable to see changes then once check any user level profile values set for this profile option. Which I doubt but check it.
If still not working, you can restart APPS Services as well once.
I think it took effect after 20 minutes?
re-login required to take effect of the profile.