I found the following workaround: I printed the PDF into a new PDF using FreePDF. The resulting PDF could then be imported into Inkscape without problems.
My original problem was that I wanted to include the graphs from igraph for R in Powerpoint as a vector graphic. As Powerpoint cannot include PDFs as graphics, I wanted to save the graphs as emf-Files. But the emf-Files exported by igraph for R look completely messed up when imported in Powerpoint. The PDFs exported by igraph for R are fine, so I wanted to import them into Inkscape and save them as emf. A bit of a long way, but it works and it does not result in an ugly pixel graphic.
Maybe somebody has similar problems and finds this useful.