Oh I have the Incase one too, and I find it way too tight for comfort. I really have to apply pressure to get it out. I tend to grab my phone out frequently so the incase doesn't seem to be a solution for me
This is interesting, as the iPhone 4 does have a smaller width. Add the bumper and you have a similar width of the 3G/3GS.
I was perusing Marware just now. Is this the product you have?
http://www.marware.com/products/iPhone-4/C-E-O-Sleeve-for-iPhone-3G
If so, this may be just the answer I was looking for. I'll just have to adjust to a vertical orientation of the phone, but that's no deal breaker at all. I just want something that protects the phone in a holster.