Agree with AllZero - visit a branch a bring a couple of forms of ID, along with a utility bill w your current address, if possible.
While there, try to find out what data collection service they're using to verify - could be something like LexisNexis. Contact the service and request copies of your consumer file. Review it for innacurate info; you should be able to dispute whatever is incorrect directly with the service. This is something you should try to straighten out now- otherwise, verification issues are likely to occur again in the future. I'd also recommend freezing your credit reports asap in case of potential ID theft.