New jungle is harder so you want to spec utility for safer early jungle clearing. You spec utility mostly for the extra potion and the lifesteal/spellvamp. This will keep you topped off in the jungle and allow you to clear safely between ganks without going low hp.
About indvidual masteries:
Phasewalker (-1 sec recall time, 1 point)
This matery is actually decent and underrated, I was just short one point. If I had one more point to spend, I would have taken this. If you recall once every 3 minutes, you save just over half a percent of your time in game, which isn't too bad for one mastery point, its always good to save time. Still, there's other things I wanted more. This mastery is nice on split pushers where the 1s recall time can save you, but maokai doesn't really play that way.
Fleet of Foot (+1.5% move speed, 3 points)
Move speed is always wanted on maokai to catch people for ganks. although it would be nice if it gave more than just 1.5%, but you take what you can get.
meditation ( 3 mana/5 sec, 3 points) (KEY MASTERY) [/b]
This is one of the better masteries in util for maokai. You have mana problems but you don't really want to spend too much money to itemize mana cause you need to be tanky. Do not skip this.
Scout (Increase the cast range of trinkets by 15%)
This mastery is garbage. I guess it helps some champs bush check with yellow ward, but you have saplings for that. Contrary to popular belief, this mastery does not increase the radius of sweeper trinkets.
Summoners Insight (10% reduced cd on summoner spells, 3 points)
A mastery I sortof wanted but just didn't have enough points for. This will improve your first jungle clear speed by allowing you to smite the second camp without waiting first, if you use a route where you beat the smite cooldown (such as the popular golems --> wraiths --> red ). Also, the reduced summoner cd is nice. I just don't think its worth 3 points, that's all.
Strength of Spirit (+1 hp/5 for every 300 max mana, 1 point)
For just one point this mastery isn't bad. Will give you about 1 hp/5 (same as def mastery) early, and a bit more later.
Alchemist/Culinary Master (Increases the duration of potions and elixers by 10%, 1 point. Potions instantly restore 20 hp/10 mana)
These masteries are pretty bad but the new jungle is a pain so I want them to keep me topped off in early clears, where you'll be buying a lot of potions. These two masteries give you 105 extra hp for your first clear which is the main reason you take them. and if you use one potion every 3 minutes there on, these give the equivalent of 0.972 hp/5 for two points, which is not the best but at least hp potions give you far more control over your health regen than normal hp/5. less will be wasted. Your effective hp in fights will also be slightly higher, if you happen to have a potion handy, esp due to the instant 20 hp boost. 20 health is worth ~50g, and this gives it instantly. But this is mostly for the first clear, you need enough hp to gank after hitting level 3 and this is an important source of that.
Greed (+1.5 gp/10, 3 points)
The typical "good" mastery gives ~40g worth of stats, so this mastery effectively "pays" for itself in 13 minutes. After that you're making bank.
Runic Affinity (Increases the duration of buffs by 20%, 1 point)
Not really essential but for only one point i think its worth it. Having the red buff longer can make your ganks better, and 30 sec of blue is quite a bit of mana to keep you topped off when camping a lane or something.
Vampirism (3% lifesteal/spellvamp, 3 points ) (KEY MASTERY)
This is really key for the new jungle, it saves you ~110 hp on your first clear, and even more for subsequent clears.
Wealth (40 starting gold, 1 point) (KEY MASTERY)
Your first clear will be 185 hp higher due to the extra potion. With the new jungle, you really need this for the added flexibility. You don't want to waste time backing before your first gank.
Intelligence (5% CDR, -10% activated item CD) (KEY MASTERY )
Quite cost-efficient for 3 points, one of the best masteries in utility.
Wanderer (+5% move speed out of combat, 1 point) (KEY MASTERY)
The top mastery in the utility partly half makes up for the fact that you can't really go boots of mobility anymore due to ninja tabi being pretty necessary in the current meta. Gives you 19 move speed out of combat once you get tabi--not bad.
I put the remaining 9 points in the defensive tree. Some notes about early def tree masteries:
Block/Unyielding (-2 damage from basic attacks, -2 damage from all sources)
These are such nice masteries but I'm sad because I don't have enough points for them. Unfortunately in the new "hard" jungle meta, you can't afford to take too many masteries that don't help your jungling. These are good for teamfights, especially early ones, but I don't have the points.
recovery (2 hp/5, 2 points)
This mastery is pretty mediocre compared to the other early tier def masteries which are all very good.
Enchanted Armor (+5% armor/mr, 2 points)
A nice mastery that scales well into late game. Early game it only saves you ~12 hp on your first clear, but once you get lots of armor and MR items it becomes much more valuable.
Tough Skin/Bladed armor (reduces damage from monsters by 2 per hit, returns 1% max hp damage to monsters)
New jungle is a pain and integer damage reduction is huge when the camps hit you for like 10-30. This can reduce the damage you take in the jungle by 10%, plus bladed armor itself is going to increase your clearing speed by ~5%. Bladed armor also works on baron/dragon, so they help with objective control too.
That said, bladed armor isn't 100% necessary as machete gives you decent single target damage. you CAN skip it, if you really, really like block/unyielding. I prefer it though, it gives you way more flexibility to gank when you want if your jungle clear is better.
Veteran Scars/Juggernaut (36 hp, +3% max hp, 4 points)
Solid tank masteries for early game and late game. Gives you extra hp for your early clear and all game long.
Oppression (reduces damage taken by 3% from enemies that have impaired movement, 1 point)
Awesome mastery, but its either this or veteran scars (+3% HP). You can't have both and still go 21 utility. Some people might prefer this to veteran scars, esp since it doesn't have the mediocre hp pre-req and you can take unyielding as well. Personally i'd rather have veteran scars and I don't want to drop wanderer either so this mastery gets a pass.