I think that people spend a lot of time focused on what makes FATE different and that they miss the very traditional core that drives the thing.
At its most basic, FATE has you roll some dice, add a stat, then compare to a difficulty. Although the curve is a bit different, it's conceptually quite similar to a 2d6 + stat versus diff system that players pick up on in like five seconds.
Then there are Stunts and Aspects.
Stunts, again, are quite intuitive. If your players have played d20, they'll probably liken them to feats. Stunts are things that let you use Skills in a way that you normally could not, or they give you a bonus under certain situations.
Aspects are where we start to see something a bit unusual. They are player defined traits which are designed to bring some narrative fact about your character into mechanical focus. Functionally, they are like a merit and a flaw glued together, but with more narrative focus. The counterintuitive bit is that they don't do anything unless someone is using a Fate Point; yes, it really only matters that your guy is "Strong like an ox" if you spend the FP on it. Some people don't react well to this.
The other thing about the game that throws some people is that movement is both abstract and tactical. People generally don't expect that. Locations get divided into abstract Zones through which characters can move. Although it is very simple to track and doesn't correspond with exact amounts of distance, your movement through Zones is mechanically relevant and your tactical interaction with them actually matters. My players caught on in a couple of rounds, but I have heard that some people just don't. Mileage. Varies. Yours may.
Then there's Stress. Characters don't have hit points. They have Stress in a couple of categories. When a physical thing hurts them, they suffer physical stress. Get enough, and they get a Consequence (such as "winded" or "I obviously landed on my face"). Consequences are more Aspects, but they are focused toward having life suck for you. This assists people in hurting you, but it also increases the number of Fate Points you get (since they need to spend them to use a Consequence).
There are a couple of other fiddly bits, but this really covers most of it. Aspects are a bit abstract at points. How things hurt you interacts with that, so it's a bit abstract. Movement is abstract. Other than that, it's not all that unusual a system. It's also a lot of fun, hugely flexible, and really robust in terms of its ability to stand up to fiddling with it.