Fedora :: SSH Not Working / Timing Out After Upgrade

A few weeks ago I upgraded one of my laptop from Fedora 13 to Fedora 14 (using pre-upgrade). The upgrade went smoothly and no errors appeared. However ever since the upgrade ssh is not working anymore. I've tried various servers inside and outside the local network. I can't contact any of them. In all cases I get:

Code:
ssh: connect to host aaa.bbb.ccc port 22: Connection timed out
I've tried to get more info using the -vvv option form ssh, but it doesn't mean too much to me:

Code:
OpenSSH_5.5p1, OpenSSL 1.0.0d-fips 8 Feb 2011
debug1: Reading configuration data /etc/ssh/ssh_config
debug1: Applying options for *
debug2: ssh_connect: needpriv 0
debug1: Connecting to aaa.bbb.ccc [xxx.xxx.xxx.xxx] port 22.
debug1: connect to address xxx.xxx.xxx.xxx port 22: Connection timed out
ssh: connect to host aaa.bbb.ccc port 22: Connection timed out

Actions so far:
- checked internet connection. No problem there. Another laptop is working fine using the same connection and the same ethernet cable. That laptop is still using Fedora 13, since I didn't want to get stuck without ssh completely.
- checked "messages" log. No messages at the time of ssh connect attempt.
- checked "secure" log. No messages at the time of ssh connect attempt.
- checked the firewall settings. The settings are exactly the same as before the upgrade (when ssh was still working). Moreover, the settings are the same as the other laptop that is working.
- temporarily switched off the firewall. No difference.
- temporarily switched off selinux. No difference.

So it doesn't seem to be a firewall or selinux problem. And I know the connection is working, so it does not seem to be a routing problem either. What am I missing here?

System specs:
- Asus EEE PC (1 GB RAM, intel atom processor);
- Fully up-to-date Fedora 14 (kernel 2.6.35.13-91.fc14.i686)