I've had no problems having my work Mac do Time Machine backups to a Windows server that has shared drives available. Time Machine puts everything in a spare image file on the Windows network drive, which I guess gets around the limitations that NTFS/FAT has.
I set it up a few months ago, but it wasn't too complex. Try googling for "time machine backup smb" or something like that.