My friend who has a 3GS is having the same issue. It's weird that only the icons do not theme. I've confirmed that the theme in question is properly formatted for Winterboard by trying it out on my iPod touch 2nd gen.
He used Spirit to JB his phone, whereas I simply used Blackra1n.