I was going to title this "not my balls," but I decided other people may find this interesting so I gave it a more descriptive (but equally accurate) title.
When I brought my Xbox from the USA to Germany, I had a little trouble connecting to Xbox Live. It was an easy fix though. I changed my locale to Germany and then recovered my Xbox Live account. Now it works just fine.