I've had problems when bringing my wiimotes over to a friend's house and connecting to thier wii. Mine are usually set for 1st or 2nd, but when becoming 3rd or 4th, I ran into a problem.
I just followed Nintendo's directions of opening up the battery cover and pressing the red button as I pressed the red button under the SD slot and everything worked out fine. (Bit of a pain to remove the battery cover when you've got the Wii Condom on though)