if you own a mac try to re format the disc to journal.
If you are on a windows like me, try to reformat the disc to NTFS. Then it will display that you need to restore as the ipod is in recovery mode. It restored with success. and voila, brand new working ipod.