There are several things to check on a Linksys router that could restrict access to the internet (none of these should be restricting you if this is a brand new router with default settings, but you don't provide much info about your situation). One is a MAC address filter, which only allows computers whose MAC address is in the list to connect. Another are the "Access Restrictions" for the router which include an "Internet Access Policy." This can be used to allow some computers to wirelessly connect to the router and get on the local network that way, but access to the internet can be restricted (or entirely prevented) via this "policy." These are all easily found, checked and modified (if necessary) in the browser interface that lets you review and change the router settings, Brand new routers should not have these issues, but it's worth checking.
As was suggested by someone else, you might not have entered the right password (or chosen the right type of security) but I believe that you would be getting a specific error message about that when trying to connect to the router wirelessly (before even getting a chance to use the internet).