I had a similar problem (on KUbuntu; Eclipse Kepler and Luna): Eclipse gave me an error message ("The type random_device could not be resolved") when I tried using random_device in my code. But building and running the project was no problem.
I then had a look at the random include file (/usr/include/c++/4.8/random) and noticed that it basically is just a collection of other includes. I then searched these other includes for the one that had the declaration of the random_device type. This file is located at /usr/include/c++/4.8/bits/random.h.
So I just added this include to my problematic header file:
And: Eclipse no longer gives me an error message! It's not a nice solution but at least it works.