Contour FCs tend to have features with TONS of verticies. Personal experience: In buiding 10ft contours for all the bare earth LiDAR data available for WA State (you can't do it with the out of the box tool BTW), I found some output contour features with over 7,000,000 verticies. That's a lot of verticies! What happens is that the clip tool needs to load these features into the RAM in order to find the XY intersection with the clip layer. Basically, these extreemly large features overwhelm the clip algorithm's ability (remeber 32-bit RAM limitation is < 2.1 GB, actually about 1.7 for ArcMap) to do the calculation.
Now in v10 (ArcInfo only maybe?), there is a handy tool called "Dice" that should solve your issue - check it out.