Hi Falko,
Thanks for your reply. Before I saw your message I went ahead and did a fresh install of Ubuntu 9.04. After this all its updates were installed without any issue.
To my surprise all my data and desktop settings including the wall paper from Ubuntu 8.04 was there when I logged into Ubuntu 9.04
(I did not select the option to format)
I really got fed up when I was not able to either update or upgrade 8.04, but now I am happy with 9.04.