So I used this solution (http://forums.opera.com/topic/514/default-google-localization) and it seemed to work.
Still outstanding questions though: Why does this issue arise? Why can't localization be changed from the Preferences.. window? And why can't I set an "Other Search Engine" as a default?