Do we view Federer's losses to Nadal on Clay (being the majority of matches they have played against each other) in a more positive light? After all Federer lost to the best player of all time on the surface! Hence, he isn't doing at all bad playing Nadal hard on all but one of the matches (I am only aware of the French Open 2008 being the only time that Nadal completely overwhelmed Federer on that surface). Keep in mind that Clay is Federer's worst surface. So playing the best clay player of all time on your worst surface - not so bad if you lose. And to get a couple of wins - well that's just cream.
If you lose to the claycourt GOAT most of the times that you meet him on clay, that's is no great knock. Not in general -- though I do think Federer should have won the Rome match in '06. He flubbed those two match points, but purely skill-wise, he had the claycourt GOAT beaten in that match.
The difference between Nadal and Federer on clay is decisive, but it is not as stark as Borg's superiority over Vilas, who is universally acknowledged as a great claycourter.
But there are also questions on how good Nadal was when he was starting to beat Federer on clay. Nadal was a teen when he was defeating Federer on red clay. My opinion is that Nadal is a superior player on clay now to his teen years. I think he has a better serve, backhand, volley and he hits harder. So how do we judge Federer's performances against Nadal in the early days when he would on occasion defeat Nadal on clay?
i would agree that Nadal got better on clay, but the bulk of his improvement as a tennis player came on other surfaces. Especially on hard court -- he went from being essentially a nobody, to winning two majors and a gold medal on that surface. His improvement on clay is not so dramatic. That's the surface best suited to his game, for one thing. And that surface is the one on which players tend to mature the earliest (think of Chang and Wilander winning RG at 17, Borg at 18, Nadal at 19). Maybe the reason for that is that a baseline game is easiest to develop when young, whereas other things like SV take longer (not that Nadal serve-and-volleys, but you get the point).
Basically I'm saying that Nadal in 2005, on clay, rather than on other surfaces, was closest to his later peak.
On the point about Federer beating Nadal when Nadal was young: those two wins, in Hamburg and Madrid, were fairly late. Hamburg was in '07, just a year away from Rafa's first straight-set sweep of RG. Madrid was in '09 and surely Nadal had hit his claycourt peak already.
I'm not sure that he's improved as a claycourter to any significant degree since '08. Maybe you could argue that in '10 he was slightly better, but I really think on clay you need young legs, and I'm not sure he's as fast today as he used to be.