Linksys WRT160N - slow connection time

I recently setup a Linksys WRT160N V3 wireless router and I finally got it working right, the only issue I'm finding is connection time.

What I mean is, the time it takes when the computer (a laptop) is started up for it to seek out and make that initial connection.

I'm not sure what the normal time-frame is for this? It's taking about 45 seconds to a minute to make that connection and often it says "it couldn't find the connection", but then finds it like 5 seconds later. I think it's almost close to timing out, or maybe even is? I restarted the laptop and tried it 4-5 times and every time the same, but it always did make the connection eventually.

Once the connection is made I get full bars on the wireless and the speed is good.

Any ideas as to why it's so slow, or how to maybe speed it up?

The Laptop is running Windows 7: Home Premium and has a Intel wireless N card.

The router is set to Wireless N only, and has WPA2-PSK enabled. I'm wondering if the security is slowing it down, but then why would the actual speed once you made that connection be fast.

I have already updated the firmware to the latest version. I did have issues even getting wireless to work at the start, I ended up resetting the whole router and starting fresh. I manually configured (which I should have done in the first place) it because I made the mistake of using the awful setup disc the first time around and it just wouldn't work.

Any help or thoughts on this is appreciated. Wireless routers frustrate the heck out of me!