An illegal choice has been detected. When changing country on user registration page.

If I require addresses on new user registration I get the "An illegal choice has been detected. Please contact the site administrator." error for the state/province field if I choose a different country. If I then choose any state, say Maine, even if the country is still Canada it will accept it and add the address to the new user. I am able to change the country after registration via the user address edit menu. I also do not get this error if I am adding a new address to an existing user.