You might want to try to Rastro this Sunday if possible. I always had great success finding gifts for people there. Spanish fans, botas, T-shirts, collector items etc....some nice gifts and some silly...even a Paella pan once
There are also many tourist type shops along the way when you walk from Plaza Mayor to the Rastro. You are bound to find something. The city of Toledo is also a nice place to shop for gifts. My last resort is always the Barajas airport (I know that is sort of cheating) and I usually spend way too much on the gift.....desperate people pay I guess. Good luck.