I was trying to setup Time Machine on my MacBook to create backup on network storage. It seems that by default it is impossible to do it, if you don’t have Time Capsule.
There is a handy command though that gives you permissions to see all types of storage in Time Machine setup.
defaults write com.apple.systempreferences TMShowUnsupportedNetworkVolumes 1
I am able to see my Network Storage in Time Machine now 🙂
Greg
Greg Gigon's wEbLOG 
If you want to set up Time Machine using a hard drive that isn’t made for Mac check here for a simple and tested method: http://www.dagaza.com/2010/03/setting-up-time-machine/