I have a 1st generation WD TV with a WD Elements 640GB HDD.
I get the "NO STORAGE PRESENT" message when I reconnect the HDD after saving new files.
Try turning the WD TV off with the remote then on again with the HDD connected.
You may have to wait for a short while but it should then find the HDD.
It will then take a while to interrogate the media if there are a lot of files on the HDD.
At least that works for me.
Hope you sort it as this is a great little device.