Broke it for me as well. I've tried everything including forgetting remotes, but the remote will no longer show up in iTunes. Has anyone had any luck with Apple? I tried calling and they couldn't help me. So much for apple having great customer support.
Also, I should note that I have two 3G iPod touches. It has broken for both after upgrading to 9.1.