In addition to contamination I would consider these possibilities:

• Reads from highly repetitive regions. These can cause problems with the assembly and the software might have removed them in preprocessing, repetitive sequences could be checked with e.g. a low-complexity filter or repeat finders (e.g. dust, repeatmasker)
• Low quality reads. Check the base quality, and get some statistics about the reads using e.g. the FastQC tool (maybe start with a subset)
• Singleton reads, e.g. from low coverage regions, if the read does not overlap with anything else it cannot be assembled
• Reads that are contaminated with vector sequences, check Blast against a vector database
• The sample is contaminated with a microorganism (alchemixt), however if the contaminant genome is small compared to the target, it might happen that the contaminant reads assemble better than the target genome. A blast search against NT might indeed help.

It is a bit hard to speculate further without knowing more details.

Edit: another idea would be to try a 'meta-genomics' approach on the left over reads if you suspect contamination. E.g. do blast against NT or NR and use MEGAN to classify the reads.

Edit2: I have been looking a bit more into validation of assemblies, and came across the AMOS genome assembly validation tool. On their website, there is a very relevant cite supporting the contamination hypothesis but also raising an additional interesting point:

Unused read information - Not all reads provided as input to an assembler are used in the final assembly. The unused reads, also called singletons, are often contaminants or insufficiently trimmed reads from the genome. Mis-assemblies, however, also lead to the presence of unused reads, as they are inconsistent with the chosen reconstruction of the genome. As an example, the reads spanning the join point of two copies of a tandem repeat are listed as singletons when the assembler incorrectly collapses this repeat. By aligning the singletons to the contigs produced by the assembler we can identify such misassemblies.

I haven't tried AMOS yet but possibly will do so soon.

I have found that crucial reads can be held hostage in spurious contigs that go nowhere when you use an insufficient coverage cutoff. Raising the cutoff can break up these bad contigs, allowing them to join good ones and in turn recruit more reads.

By the way, reads from repetitive regions such as retrotransposons generally do make it into assemblies (into small contigs of incredibly high depth), but they destroy any possibility of determining gene order. That is why people (especially on the plant side) still sometimes rely on sanger to "sequence through repeats" - i.e. connect regions flanking repeats.

In addition to the other valuable comments, have you evaluated a different assembler? Some assembliers (ALLPATHS-LG, MSR-CA, etc) do a better job of error correction than others, and thus use more of the data.

In addition to Michael's answer. You might want to check for badly CLIPped sequences. For instance adapters at wrong locations..... Illumina mate-pair PE libraries are famous for those artefacts.

We routinely check against a set of bowtie genome indices including vector (as suggested) but also a DB with commonly used adapters. You'll be surprised.....in the bad way...

Have a look at for instance the fastq_screen tool

Dit you check a sub-set of the non-assembled reads what it is (e.g. by BLAST)? Even though no reference is available....you might not be the first to be surprised by a contaminating yeast or bacterium...If that is the case; the answer is simple: trash it.