There's already been discussion in this forum about the Noreve and Krussel cases for the 3125. A question about a good case for the 3125 came up in another topic so I thought I'd post here where it could be found easier.
Personally, I like a holster to just hold the phone while not being used, so I don't get the kind that stays on the phone but rather the phone just slips in and out of a pouch. The one I got (and like a lot) is made by Cellet and is actually sold for the V3 (RAZR) but fits the 3125 fantastic.
I just did an eBay search and found it
here. As you can see it has white stitching, but they also have a similar solid black one from the same seller as well as a flap-less version.
What I specifically like about the pouch I chose is the entire flap is magnetic. You don't have to find the little magnetic button/snap to "lock" the flap. It's a strong magnet too! Just get the flap about a couple of inches or so from the pouch and it snaps closed very firmly.
I like it and wish they had one similar for our other phone. I can't say how well the others fit, other than the white stitched one is great!
Devices: T-Mobile MDA (Cingular SIM), i-mate SP5m (sitting in a drawer at the moment while I attempt to migrate to PPC permanently), Cingular 3125 (unlocked and in use on T-Mobile), Motorola MPx220 (retired), Motorola MPx200 (retired)
Accessories: Plantronics Explorer 330 & 2G Patriot Micro-SD (use w/MDA), Kingston 2G mini-SD used in SP5m, Plantronics Discovery 640 & 2G San Disk micro-SD (use w/3125), Jabra A210 BT adapter + Motorola HS805 (retired)