Radiohead have certainly written music that IS prog - all of OK Computer (not just Paranoid Android), and some of The Bends and the Iron Lung EP), but find it difficult to consider them a prog band.
Before OK Computer they were essentially a "progressive Indie rock band" that wrote some stunning hit singles (Creep, Street Spirit, Iron Lung, High and Dry, Just), but they then went through a deeply experimental period. I think they realised that this was such a strong album that they had to completely smash apart everything they wrote or fall into the trap of writing "more of the same". Kid A and Amnesiac are albums I am still struggling to "get", as there would seem, on the surface, to be little musical craftsmanship in the same way as OK Computer. Hail to the Thief is a welcome return to the form of Pablo Honey - ie prog indie.
OK Computer is only overrated in the same way that Dark Side of the Moon or Abbey Road are overrated, IMO