I can't comment on the deal you got, but the dealer is not telling you the truth about the credit history. Harder to qualify for a car loan than a mortgage? Give me a break. Unless you had to pony up bank statements, W2s, 1040s, pay stubs, etc. etc. and a blood sample, getting a car loan is 10x easier than a mortgage.
The fact that he called yoour score a Fake score? Give me a break, you could have just one credit card that's open for 6 months and have a true FICO. Sure, it might be a very thin file, but you would have a FICO nonetheless. You've got nearly 5 years of history with two cards. You very much have a real, true, FICO score.
Did you by chance walk into the dealer by yourself?
Given the above, I'd take anything the guy told you with a very, very big grain of salt. I'll let others comment on the deal you got and whether you should return the car, good luck.
Starting Score: EQ 773, TU 766
That is an excellent rate:
- First time buyer
- Used car
- Hardly anything down
I'm not certain why you'd feel <4% APR is a bad deal? That's lower than a mortgage which is about the cheapest money anyone will ever get.
As for harder than a mortgage: no in the respect others have stated, in that fashion an auto-loan is probably the easiest of all loan products to obtain; however, getting a rate equivalent to what a mortgage is offered at, is a much harder challenge, especially with your history and the particular car involved... so while it wasn't a complete truth, it wasn't an outright lie either by the salesman in this case.
If you are concerned about the overall cost of the car, go look it up on Kelly Blue Book (kbb.com): if it looks reasonable (remember CPO are more expensive and you'll need to selection that dealer sale optio), go on with life happy.
@Anonymous wrote:Definitely a great point regarding the interest rate, which was very good, although he had a similar rate from his bank pre approved. Usually those kind of rates don't come except through special financing programs through the car manufacturer. However, my credit union that I will be trying to refinance through this summer actually offers 2.49% for loans up to 60 months. I guess my point is, you can get better interest rates through credit unions, but that is great through a dealer on a used car for sure.
Yeah, just on a used car, I mean no offense (and my scores are lower than yours), but I don't think a CU is going to give you that rate: usually the rate they list is the best offered and there's fine print attached. Let me know if it does though, I may see if I can open an account for when I refi in a few more months! 
I looked up the local So Cal price (in a moderately expensive neighborhood) on KBB for that car, and it was north of 20K. Depending on location, I suspect the OP got at least a reasonable deal.
Sorry, forgot to add that I probably would not be approved now. However, this credit union I think uses EX. Within 3-4 weeks, my EX and EQ files will both be squeeky clean and my scores for those two should go up nicely. I am also paying my utilization down from 80% to 5%, which will be a huge boost to my scores. I hope to have at least a 650 before I apply, although obviously I won't know since I can't check my EX 