So the connection you have is purely via the built-in samba server - AFP access, as required by TimeMachine, is advertised via a protocol known as Bonjour and your Mac is not receiving those advertisements, else you would see something similar to my screenshot. Doublechevk that AFP is enabled on your NAs, but the most likely cause is your router - some routers simply do not seem to work well with the method employed by bonjour, particularly over wireless, and this is purely a fault of the router (Sagem & Thomsonrouters appear to be particularly affected by this issue)
You may be able to fix this if your router has settings related to broadcasts or multicasts that you can configure. Check if there is a firmware upgrade for your router also. Else the solution will be to wire your Mac to the router rather than use wireless (usually works, but not always) or to invest in a better router

