General Server Lag (Highly CPU intensive at times)

Everyone (and I mean everyone) on my 100% 1.7.2 Vanilla server is getting general server lag.
(This includes block lag/mob lag/chat lag/movement lag etc.)

I run the server on a dedicated CAT6 line. (http://www.speedtest.net/my-result/3059882600)
Even when connecting a local client with localhost it has this general 'server lag'.

I can't quite pinpoint the cause of the lag as of yet, but we really only started noticing it since 1.7.2, I've been keeping the server updated along with the snapshots and they seemed fine right before.

I tried disabling all redstone devices.
I tried staying in some of the same loaded chunks.
I tried kicking everyone off.
I tried dedicating a whole 5Gigs of RAM to the server.
I tried dedicating a whole 8Gigs of RAM to the client on another computer with similar specs.
I tried giving the Java Runtime High priority.

Nothing shows in the server log as going wrong however it does constantly show that it can't keep up.
(http://pastebin.com/PtehcSde)