That sounds like one of the more interesting problems. A crystal that fails to work WITH capacitors?
I've designed boards that use PICs, and I've never had problems with the caps or the crystal running. However, here at work, we use 80C51 variations, and the order of the day is to use a one meg resistor across the crystal's leads. What the difference between these chips is eludes me, but crystals come in different varieties, and this resistor may do the trick.
Good luck with your project.
kenjj
Oops! I saw the response to the OP's question and realize he's right. Disregard this post.