1) Hard to give the PCs fate points - They use them quickly and it's hard to give them some kind of inconvenience every scene so they can get them back.
Remind them to self-compel. Off load some of the responsibility.
Also, don't forget playing their character's flaws can often be seen as a self compel. When Bob tries to rescue a bystander, is it a random act or a self compel of some 'heroic' aspect?
2) Having to use fate points to gain bonuses - So one of my characters wants to take cover in a fire fight but he has no fate points to tag the aspect 'crates.' As I understand it, you can't use an aspect unless you have fate points. Seems very counter intuitive.
First, my version of the official reasoning - you're simulating a scene
in constant motion. He rolled behind cover in one exchange and kept rolling (or his opponent moves to negate it) by default (unless there's another fate point spent). It's a system that, in my opinion, actually works better if you leave combat abstract and don't map it. Finally, don't forget the free tag on maneuvers.
For an alternative, you might look at Strands of Fate. It uses a sticky aspect concept which allows free tags of an aspect across multiple exchanges. Sticky aspects are more difficult to create but it makes sense to me.
3) Complicated magic system - anytime the wizard wanted to do something, it took a while. And I have to admit, I often got fuzzy on how if you succeed on a evocation, do you add in the power to the success of the casting? I just felt like it could have been made simpler.
This, in my opinion, is caused by the overly verbose writing style used. I rewrote the evocation rules to fit on a one page pdf. Thaumaturgy takes a second page.
4) Looking up powers - it was tough looking up stats for villains. there was sort of a little cheat box at the bottom, but I had to go to the other book to look up what powers they used. I ended up making my own monster sheets with power descriptions included.
I suspect this will go away with familiarity but it is worth a short sentence / reminder on your villain's sheet.
Edit: There's also a two sheet powers reference
downloadable from Evil Hat. There's also a short 'reminder' version of the spellcasting rules.