Was the iPod connected to the computer when it was formatted or was it reset from the iPods menu?
If it was reset from iTunes can you tell me if your songs are still in the iTunes library?
In that case can you open iTunes then connect the iPod to your computer and wait till it appears on the laft hand side.
When it appears can youthen click on it and you should then have a Restore button appear on the left hand side of the screen.
If you can select that and then allow the restore process to run it will reload the firmware back onto the iPod and once finished you should then be able to unplug it and use it like normal.
If that does not work or if you have any issues please let me know
In that case if you wish to stop I will have this question closed for you.
Hopefully we can be of more help next time