Problems once wireless is secure

This may be a really simple question, but I am not as savvy as you
guys are, so here goes:

For the past few months I have had my Toshiba computer upstairs
connected to my cable modem via my wireless router while my wireless
router provides the internet to my other Mac laptop in my basement.

So, my Mac in my basement was getting wireless, while my Toshiba
upstairs is directly connected. Everything was just dandy.

However, my wireless was not secure. Things worked well, but I had
been uneasy at not having secure wireless. So I secured it by creating
a password.

No problems with my Toshiba. But my Mac will now not connect to the
internet and occasionally does not even 'see' the wireless. The only
thing that makes it work is if I reset my cable modem and my router,
then my Mac connects successfully. But this lasts perhaps only for an
hour or two, then the same problem happens again.

I thought this may be a Mac specific issue, but I have a wifi Palm
Tungsten and the exact same problem happens. When I reset my router
and cable modem, my Palm connects to the internet for a few hours,
then does not connect. So it is NOT a mac issue, it is likely a
wireless router issue.

All the while, my Toshiba (directly connected to the modem) works just
fine.

I called my ISP, but they said that they do not deal with 'wireless
issues' as that is not 'their' problem.

My brother had mentioned something about static and dynamic IP
addresses, but I have no clue (and I think he does not either). I'm
not a technologically advanced guy, just trying to do some work on my
computer.

Help ! Please ! I'm going crazy !