Rack (& Pannier) for a bike with disc brakes
2019 Update

Racks specifically designed for bikes with Disc brakes have become much more common. It shouldn't be hard to find something now.

Original 2011 answer

I think the LBS is partially correct, that bikes with disc brakes aren't generally designed to hold a rack.  That said, I think there's a few solutions (other than getting a bike built to have disc brakes and a rack):


Get a seat-post (or similar) mounted rack.  Downsides: very low weight limit, often not good at holding panniers, and probably prone to spinning around.
Use "p-clamps" instead of the built-in holes.  These are rubber-covered clamps that would go around the seat stays to give you a hole for a rack up above the problematic disc brake stuff. This is more usually done on bikes that simply don't have a place to bolt anything on. Downsides: may put the rack too far up, may put the rack too far forward, may slide, may not be as strong.
Spacers and a longer bolt with a somewhat wide rack. So that the rack's stays run to the outside of the brake hardware.  It seems to me that too much weight would tend to try to bend the bolts down and the holes up.  Would be much better if you could find a rack that could use both holes.
I don't know the right term, but it might be possible to find a metal piece that screws into both of those holes and gives you a new hole behind that location.  I've seen some racks mounted like that to get the rack back further for more heel clearance.
There are racks made to go on bikes with disc brakes.  The one I found first ( http://www.topeak.com/products/Racks/ExplorerTubularRack_discMount ) basically has the spacer I suggest in #3 built in.  The second one I found ( http://www.tubus.com/en/rear-carriers/disco ) basically comes into the holes from behind instead of directly above, like I suggest in #4.


A rack specifically designed to mount on a bike with disc brakes would be best, of course.  The other options might be cheaper.