Here is an educated guess of the problem.
The SSN consists of three parts, Area, Group and Serial
AAA-GG-SSSS
Just about each month SSA puts out a High Group list, which shows the highest Group number that has been assigned within each SSN Area. Either your SSN is from a Group within your SSN Area that has just started to be used and is not on the current list or the company is using an old list.
This is July's list:
http://www.ssa.gov/employer/HGJuly0306.txtPrevious months:
http://www.ssa.gov/employer/ssnvhighgroup.htmThis shows the order in which Groups are used:
http://www.ssa.gov/employer/ssnweb.htmIf it's not on the July list hopefully it will be on the next list. If it's there and it has an * next to it, that is a change from the previous month and the company is probably using an old list.
Now the employer can call the SSA 800# and verify your SSN if they have hired you. They just need their EIN, your name, SSN, date of birth and sex. SSA just says whether the info matches or not and when it doesn't match they don't say what didn't match.
You can also go into your local SSA office and ask for an SSN Verification Printout. The Printout will verify the SSN and name on your record. If you say it's for an employer there is no charge.