Don't feel bad, igorsky. You're not alone. I can't get my phone to sync over wi-fi either. Been following the prompts here and have the same experiences as you. I am using Windows XP. Could this be the issue? I read that iCloud is not supposed to work on XP. The first time I clicked SYNC NOW it looked like it was working, but then I got the message that it was waiting for my computer to become available. It was and is so not sure why it's not working.
Yeah this is really driving me crazy. It's always frustrating when you seem to have everything set up correctly and can't get it to work.