Try Bike Centre Pfennings. Go out of JHQ through A Gate, turn left at the lights onto HardterStr and then right at the lights through Hardt. Keep going through Hardt and out the other side, you'll reach a dual carriageway. Keep going to the next set of lights, and on your right you'll see a 24hr gym called McFit. Turn right there, and after about 300m turn left over a little bridge. Its there on your right.
Sounds like a f*ck around when you consider there's a PX on camp, but the bikes in the PX are shit and only last a couple of weeks. I got mine and my wife's bikes from Pfennings about three years ago, never had a drama. good quality stuff.