what 'new' batteries did you use? I've seen similar issues with just about every battery in a variety of different remotes (that use AA or AAA) aside from Duracell Ultra's. cheap batteries (and even many name brand batteries) are prone to issues even when they are brand new.

May still be just the unluck of the draw, but make sure you're using good batteries (not just 'new' ones).