Did Naddodd really discover Iceland?

The better question to ask would have been 'Who discovered Iceland?'. In this case, where we have to think about Pytheas, I would argue for 'No', while my answer regarding Naddoðr would be the same. Regarding my own question, the answer that seems most plausible is that we don't know.

Pytheas

The main and primary problem when we think about Pytheas today is that there are no extant writings from him—the only thing we have are quotations by authors who (mostly) disagreed with him. This means that a lot of specific information about his travels has been lost. As such, it is very difficult to determine where specifically Pytheas went and attempts to do so have been carried out for a long while.

There's a lot of reading available on this, but I'll synthesize the most believable accounts I've read about (specifically, Talvik): namely, while Pytheas circumnavigated Britain, he then moved along the North Sea coast into the Baltic Sea (and did not visit Iceland). The references to "marine lung", "midnight sun", and "amber" all make it more likely that Pytheas travelled extensively on the Baltic Sea coastline from the mouth of the Vistula up towards Åland (a possible final destination). In this case, Courland may have been mistaken for a large island (as some of the descriptions mention large islands in the 'northern seas'), and Thule could represent Saaremaa.

The benefits of this account are that marine ice (of any kind) is generally accessible far further south than in the open seas around Norway and Iceland, but also that travel along these shores would have been far easier in Greek times (who were mostly unwilling to stray into open seas), and possibly Pytheas would have learned of "an island" or "a people" further ahead due to preexisting trade relations when he moved through these regions. On the other hand, Iceland had no permanent settlement so striking out into the sea to discover it in 6th century BC would have been an act of serendipity—with a far larger chance that the explorer be lost in those seas. Not impossible, mind you, just far less likely. Unless we actually discover all of Pytheas' writings, we cannot know for certain.

Naddoðr

The accounts we have regarding Naddoðr's exploits are more plausible. Namely, two Icelandic founding texts, the Landnámabók and Íslendingabók, describe the Norse to be the first settlers of Iceland. In the Landnámabók, the discoverer and first settler (though unwilling) was Naddoðr (Naddod/Naddoður) who saw no signs of other humans on the island. This expedition is dated to the 860's. The main problem with the Landnámabók is that it was put down at least a few centuries after the actual events with the oldest surviving copies dating to the 13th century. While it is likely oral tradition would have preserved Norse stories, these can't be considered accurate.

The Íslendingabók, meanwhile, starts out with an already discovered Iceland that's only awaiting settlement. This first settler was Ingólfr, but admittedly this does not get us any further with respect to this question. However, already in the first chapter, Ari Þorgilsson writes:

At that time Iceland was covered with woods between the mountains and the seashore. There were then Christians here, whom the Northmen call papar, but they later went away, because they did not wish to stay here with heathens; and they left behind them Irish books and bells and staffs. From this it could be seen that they were Irishmen.

These papar are, therefore, likely to have already lived on Iceland, but there's no easy way of proving or disproving this. In short, we don't know until more evidence is unearthed. However, even without a specific reference to the papar, archaeological findings point to at least semi-permanent settlement of Iceland since the early 800's as evidenced by longhouses in Stöðvarfjörður which are dated to approx. 800. This would invalidate the Landnámabók claims that Naddoðr discovered the island.