eBay didn't say what kind of encryption they had, only that they were encrypted. Personally I'm more concerned about the personal information in the leaked data that wasn't protected at all! So sure, change your password, but it won't change the fact that someone got your name, email address, physical address, phone number, and date of birth.