Did you install any toolbar recently,if so,try to uninstall it and see if you can change the search engine or not.Feedback plz.
some AV crap behaves very funny and so far it can alter browser permissions for example which leads to problems like OP has