I have been very happy with the TripleTreds on my '04 and the handle the snow well. Did you make it through the winter on the OEM's fairly comfortably? If so, I don't think you need a lot of snow traction since they basically have none.
Bob Wilson had a recent thread on the same subjuct pointing to the
Consumer Reports site with a review of All Season tires. It would be worth a look. For the money the Yokohama AVID TRZ looks really good.
TireRack has them for $54, the CR article has them listed at $70. It has a VERY directional, asymetrical tread pattern. If you get them, make sure they are mounted properly

The TireRack price on the TTs is ~$93 , whereas the CR review lists them at $80, must have been a big price increase recently.