Don't use N-only mode. Set it back to Mixed. N-only mode sacrifices range for speed. The older modulation schemes from the A/B/G days sometimes work better at range, so it's good to leave them enabled so that even N clients can use them when they're the best choice.
Also, I'd be surprised if your router really has a 40MHz-only mode, as the IEEE 802.11n standard does not provide for that. The standard only provides for 20MHz-only and 20/40 modes, but no 40MHz-only mode. If you router really does have a 40MHz-only mode and you've set it that way, change it to 20/40 so that devices on your network can choose 20 or 40MHz transmissions as it suits them.
KCotreau is right that all else being equal, signals in 5GHz don't go as far as signals in 2.4GHz. However, due to varying regulatory agency rules for different frequency bands, and varying radio designs, some APs may well be able to transmit at higher power in 5GHz to make up the difference. BUT, the specs on your Linksys WAP610N say it has higher power, higher sensitivity, and even a slightly higher-gain antenna in 2.4GHz.
Look at this table from your User Guide:
RF Power (EIRP) in dBm
802.11a: 15 dBm (typical) @ 54Mbps
802.11b: 18 dBm (typical) @ 11 Mbps
802.11g: 16 dBm (typical) @ 54 Mbps
802.11n: 12 dBm (typical) @ 130 Mbps (HT20),
270 Mbps (HT40)
Receive Sensitivity in dBm
802.11a: -72 dBm (typical) @ 54 Mbps
802.11b: -85 dBm (typical) @ 11 Mbps
802.11g: -73 dBm (typical) @ 54 Mbps
802.11n: -70 dBm (typical) @ MCS15/2.4 GHz,
-69 dBm (typical) @ MCS15/5.0 GHz
Antenna Gain in dBi
2.4 GHz: 1.58
5 GHz: 1.45
Note that in decibels, a gain of 3 dB is a doubling of power, so this is saying that it puts out 4x as much power when transmitting at 802.11b rates than it does when transmitting at 802.11n rates. (Too bad it doesn't say which band those N rate power levels are for, so I guess we'll just have to assume the same number applies to either band, which seems unlikely, but whatever.) It's also saying that it can successfully receive B-rate transmissions that come in at just 1/32nd the power of the quietest N-rate transmission it can receive.
So it looks like, for this device, you'd have a huge range advantage by going back to the 2.4GHz band and re-enabling the legacy rates (just leave the "Network Mode (2.4GHz)" set to "Mixed"). Also leave the "Transmission Rates" set to "Auto".
Be sure to pick a clean channel (or leave channel selection on Auto and hope your AP does a good job of picking a clean channel).
Also, when doing 802.11n in the 2.4GHz band, you should consider using HT20 (20MHz-wide channels) only, not 20/40 or 40-only. This is because the 2.4GHz band is small crowded, and the channels overlap. If you use 40MHz wide channels here, you're using up 2/3rds of the band, and that doesn't leave much room for coexistence with other networks, or Bluetooth devices, or 2.4GHz cordless phones or baby monitors or whatever. It means you're only going to get 130-144 megabit per second signaling instead of the 270-300 megabit per second signaling your N gear could be capable of, but it might make everything work out better anyway by reducing interference.
P.S. I just looked some more at the US English user guide for that box and oh boy is it terrible. It's clear the writer doesn't know the 802.11 concepts he's trying to write about. But then again, I don't think the web GUI engineers knew what they were doing either, because I can't believe the product provides a non-standard 40MHz-only mode without providing a standard 20/40 mode. I'll bet that what the User Guide and web GUI call 40MHz-only is actually 20/40 if you look at it with a sniffer. It's also weird that they use the channel number of the center frequency of the wide channels. Almost everyone else in the industry tells you the channel number of your control channel, then says +1 or -1 to tell you if your extension channel is above or below your control channel.
Best Answer
OK, I seem to have solved the problem by:
Now I can see the SSID being broadcasted and I can connect to it. I hope this will hold.
Since I had already tried to perform a reset with no result before that, my guess is that the application "Network Magic" was somehow interfering and causing this problem... It's only a guess though.