I'd suggest PVD (diamond) coated tooling for graphite. Depending on the brand, you could spend 3-4x as much per cutter... but see 20-30x the tool life, so it's really a no brainer as graphite is quite abrasive.
Run as much rpm as you've got and keep an eye on speeds... mainly due to the fact that many older machines don't have the look-ahead capabilities. Mill a square at 300 inch/minute and what you end up with is 4 flat edges with large sweeping radii leading into each corner, IF you don't have the loo-ahead capabilities and/or lots of slop in the machine.
Good luck,
Chuck
The Manufacturing Reliquary
http://cmailco.wordpress.com/