I've heard of some people getting their old silicone cases to fit on the new Iphone 3Gs but for the most part, they won't fit and you'll have to get a new one made for the 3G model. Try it first...it can't hurt.
For myself, i went with an Invisible Shield along with a Macally mClip holster.