It seems every Linux machine I've ever worked on, when the router was restarted, the computer required a reboot too. All the Windows machines rejoined the network just fine. Why won't my Linux computers recognize a restarted router without a reboot themselves?
EDIT: I run 10.04, it's a desktop, wired connection, the router is Windstream 2Wire I'm not sure what model but I did find "2701HG" on it. I'm not sure what PC hardware is relevant here, the motherboard?
It will.
If it doesn't, it seems you have encountered a bug or an error in the driver.
If this bug is in a proprietary wireless driver (see System → Administration → Additional Drivers), I'm afraid there's not a lot you can do about it apart from writing an email to the manufacturer.
If this bug is in an open source driver, you should report the bug so that it can be fixed. Usually, those bugs will be taken up-stream to the relevant developers, since Ubuntu doesn't provide the drivers themselves.
In the usual case, the network-manager will connect automatically to any wireless network within reach. It will roam you through different networks if you're moving around the house, it will detect which networks you've joined successfully and automatically connect you.
If, in your case, the Network Manager doesn't automatically connect to your network after the connection has been lost, please ask a question about it here. Make sure to provide us with all the details about your connection, your wireless hardware and the drivers you use. Also, provide all the steps to replicate the problem.
Note: I talk about wireless networks, but this applies equally to Wired networks, 3G connections, Modem connections, even VPNs. To the Network Manager, they're all more or less the same.
you might need to restart network-manager if you're on a desktop system
sudo service network-manager restart