So 10.5.4 came out and me being the sucker that I am I installed it to see if it would sort out some of those issues I was having. While it does appear to help with the slow shutdowns (no need to remove the sleepimage file every now and then anymore?), it does not fix the issues with Starcraft or Diablo II or any other application that requires 256 colour support for that matter.
There are some solutions floating around on the net, that basically involve replacing the kexts from the 10.5.3/4 update(s) with those from 10.5.2 but this seems like a bit of a kludge to me, so hopefully this will be addressed officially at some point. Hopefully before Starcraft 2 comes out :)