Maybe I'm too late but...
I stayed two years ago in a beautiful rural hotel in Aldea del Obispo (mentioned in some maps as Aldea de Trujillo) called El Tenado (
http://www.eltenado.com ). It has only 6 rooms, in rural style but with all modern amenities, all named after birds because they are specialized in birdwatching tourism. It is located 10 kms. North of Trujillo and 30 kms. South of Monfrague.
If you prefer something more 'high tech', I'd recommend Hospederia de Monfrague
(
http://www.alextur.net/hotel/monfrague/ ). It is closer to the park than the other hotel I mentioned. It is a newly built hotel with design furniture and decoration.