The original K-Cups are made from plastic resin 7, the catch-all 'other' plastics category. This means that the precise composition of the plastic is known only to the manufacturer. Because of this, plastic resin 7 is hard to recycle and usually goes to landfills. A second problem is that the K-Cups consists of several materials that need to be recycled separately but cannot be separated easily (e.g. foil lid, plastic cup, filter, used coffee grounds).
So in short the answer is "No, K-Cups are not recyclable".
On their website Keurig confirms this:
We are very sensitive about the waste created by the K-Cup® packs and are investigating alternative materials. Finding a solution for this is a priority for us, and one we hope to have before long.
Keurig does have a slightly better system, the Vue capsules that can be recycled more easily, that is if your local waste processing facility recycles plastic resin 5 (Polypropylene).
However, according to this treehugger blog, all cups, even the onces that call themselves recyclable, usually end up on landfills because
The cups are then recyclable — in theory. The problem is the cups are too small to be captured in most recycling facilities where machinery separates objects by size and density
UPDATE August 25th 2016: Green Mountain, the producer of K-Cups, recently launched their first recyclable K-Cups. The new pods are made from polypropylene (plastic #5) and Green Mountain claims that the
new recyclable K-Cup® pods have been tested in real world recycling and recovery facilities