Is there any reason why Time Machine only finds my NAS over wifi?
I believe the issue you are referring to is the fact that the only drives that you are allowed to use as a time machine are ones that are internal to a Apple router, the only way for this to work is if you had an Airport Time Capsule which has a built in hard-drive. That is the only drive Time Machine supports connected to your router. 

Basically you CANNOT use a drive hooked-up via ethernet to your router for Time Machine. You have to have a Airport Time Capsule and use the internal hard drive. That is why when you connect your NAS Time Machine does not recognize the drive.