I was just playing around with this again and remembered that in the past, having external drives connected could cause the computer to shutdown slowly, one of the things that didnt occur to me until now though, was that my Windows Bootcamp partition may be an external drive of sorts, or at the least, may be affecting the shutdown cycle.
So I ejected it and then tried shutting down. The computer now shuts off in 15 seconds or less as opposed to almost a minute before, it still doesnt seem as fast as a new install of Leopard but its definitely a big improvement.
The question now though is why or what is it doing with the Windows partition before it shuts down? It also possibly invalidates the earlier line of research I was following with the menu applets, so clearly I need to look into this some more but its the first definite improvement I have seen.
If you try this and it improves your shutdown speed please let me know, it will be interesting to compare.