I can find my network, and the signal strength is strong, but it barely ever connects, and if it does, the connection doesn't last long. I just bought a new router, so that shouldn't be the problem. My laptop is only one year old. This has been going on for over 6 months now, and before that the connection worked well. I cannot think of anything that has changed that would cause interference.
When troubleshooting on MSN Messenger, it sometimes says Default gateway is offline.
If there's anything other info that would help solve this problem, please let me know.

Do you live in a densely populated area?

What model is it?

Do you have an encrypted connection?

There are several causes to that type of problem, please respond to those questions, and I will see if I can help more.

I have been having this problem for over 6 months now. Nothing has changed that would cause interference. I recently bought a new router to see if that was the problem, and it is just as bad. I can only connect about 10 % of the time, and when I do, I usually either lose the connection shortly after or have only limited connectivity. My SSID (network) is visible when trying to connect to the internet, and the signal strength is very strong.
When using MSN explorer troubleshooter, it sometimes says that my gateway appears to be offline.
My laptop is only a year old, and I'm am trying to connect wirelessly to my computer in the basement. Please let me know if there is any other info that would help resolve this issue asap.
Thank you in advance.

What signal strength do you have? Look at the "bars" and see if it's weak. If it is, can you move the gateway so that the signal doesn't have to go through as many layers of whatever it goes through. How far away is the gateway and how many walls are between the computer and the access point?

Yes I live in a densely populated area, but I did before (haven't moved) and didn't have this problem.

My laptop is Toshiba (Satellite A300), my new router is Linksys Wireless-N Broadband Router.

My encryption is WPA2 I believe, and is set to TKIP or AES.

Thank you for your help. Please let me know if there is any other info that would be useful.

The signal strength is high. The bars are usually full, or almost. The router is in the basement, and the laptop is on the main floor. Not too far from each other. That's what's confusing me.

Try changing your wireless channel. You will find that in densely populated areas there is a lot of interference. The newer linksys routers seem to be especially susceptible of this (personally I think it is because of the antenna-less design).

I was wondering if you had security, because I had considered people were leeching off you, but that doesn't seem apparent. You can check online to see if there is a firmware upgrade for your router. That may help.