Well I don't have a HDTV so I have no real idea about what could be causing your problem. Try reconnecting everything or using another HD source (xbox360, SkyHD etc) to determine if its the TV or the Wii itself.
In relation to your guessing that 480p is HD you were semi-correct (480p is not technically HDTV but actually EDTV.The reason being that the p stands for progressive scan which means every line of the picture is drawn out in order (1,2,4,5,6,6,7,8,9,10 drawn in 1 refresh of the screen)
The i stands for Interlaced scan which means every second line is drawn then the missing lines are drawn (1,3,5,7,9 drawn then lines 2,4,6,8,10 are drawn)
As a result Progressive scan offers better picture quality than interlaced because using interlaced scan causes details to 'twitter' so anti aliasing is used to smooth the picture and this comes at the cost of the resolution and thus, quality.