Goose Search Yahoo 404 Redirect

On both my iPhone and my Mac OS X 10.6.8, whenever I use Safari (and also Firefox on my Mac) to Google anything, I get redirected to a Yahoo 404 error page.

I tried using Chrome on my Mac and it works fine.

The problem started on my Mac when I was trying to sync iCal to my google calendar. iCal wasn't connecting to google calendar, and I sought out advice on the web, and tried a few different things, including deleting the keychain info for google (as one site suggested).

After that didn't work, I thought I put the info back into Keychain properly, but after restarting my computer, that's when Google search starting acting up.

I don't know what I could have ever possibly done to my iPhone to be having the same exact problem.

Please help!