After further investigation I have found that the CPU Time also counts CPU Waiting time.

The 2nd SP that increased frequency massively, but not CPU usage was probably adding contention to the CPU for the 1st SP, increasing the CPU waiting time.

We had a large number of waits of type SOS_SCHEDULER_YIELD (240 per sec) during that period which also suggests this.

http://www.confio.com/logicalread/sql-server-sos-scheduler-yield-wait-type/#.U0_AjoVxhiY

"Plans that process large data amounts (large scans) can often require many cycles of CPU to ‘process’ all the data. This could lead to higher SOS_SCHEDULER_YIELD waits as it has repeating cycles of running and yielding, reducing the amount of data to be processed (for example, turn those ‘Scans’ into ‘Seeks’), and can often reduce the # CPU cycles required and thus amount of SOS_SCHEDULER_YIELD waits."

Also I found that the 1st SP needed a covering NC index as it was performing an index scan on a 1M row table. That table was also the main table in the 2nd SP, but im not sure that would have added to CPU contention. Both SPs are simple selects.

I'm not sure how the 1st SP that was missing the index managed to fly under the radar for so long...