If you're absolutely certain you are using the precise same password (no variation in capitals, for example), then you might try deleting and re-adding the iMessage account to see if that resolves the issue. Otherwise, you'll have to give Apple a call about it.