Regular Expression Magic
Sven: The behavior of [foo] expansion in regular expressions depends on your locale. In the traditional Unix C locale, [A-Z] is [ABCD...], but in other, newer, fancy-shmancy locales, characters are sorted in dictionary order, so [A-Z] is annoyingly [AaBbCcDd...], which is probably not what you want.
So you can set LC_ALL to C before running sed(1) and you should be good to go. This is probably the difference between the different distributions: different locales.
You could also use named character classes. I believe that [:upper:] means, in a nice locale-independent manner, all uppercase letters, where as [:lower:] means all lowercase letters. The brackets are part of the named character class, so if you want to specify the equivalent of what you and I think that [A-Z] means, you would do [[:upper:]].
Hope that helped, duder!