Olive oils vary significantly in flavor depending on the varietal and where it's grown. I personally hate the taste of Greek EVOO -- my favorites seem to come from California. But there's nothing that says you couldn't make an infusion with the less-than-delicious oil you already have. You could always add some dried herbs and thinly sliced garlic to the EVOO, put in a dark cabinet for a few weeks (shake every now and again), and then give it a shot. It might be more "Mmmmm!" than you remember it!
Mark recently did an article on Macadamia nut oil, which I would think would be amazing on salad as well as totally Primal.