Does your ISP gives you dynamic IPs? Then you most likely will need to use a dynamic IP services (such as dyndns, noip, etc) and use something like ddclient to send the ip updates to the service.

With me, both statements are true, but there are solutions:

1) My ISP blocks port 22
Solution: I defined an aternative port in /etc/ssh/sshd_config

2) My ISP changes IP address
Solution: Register at www.dyndns.com and instal inadyn to automatically update your dns entry when your IP changes

nope. my IP address is static. I have an E1 connection that is a leased line.

Maybe post outputs with:

netstat -anp | grep sshd
cat /etc/hosts.allow
cat /etc/hosts.deny

as requested.
root@Asterisk001:~# netstat -anp | grep sshd
tcp6 0 0 :::22 :::* LISTEN 3303/sshd
root@Asterisk001:~# cat /etc/hosts.allow
#
# hosts.allow This file describes the names of the hosts which are
# allowed to use the local INET services, as decided by
# the '/usr/sbin/tcpd' server.
#
# Version: @(#)/etc/hosts.allow 1.00 05/28/93
#
# Author: Fred N. van Kempen, <waltje@uwalt.nl.mugnet.org
#
#

# End of hosts.allow.
root@Asterisk001:~# cat /etc/hosts.deny
#
# hosts.deny This file describes the names of the hosts which are
# *not* allowed to use the local INET services, as decided
# by the '/usr/sbin/tcpd' server.
#
# Version: @(#)/etc/hosts.deny 1.00 05/28/93
#
# Author: Fred N. van Kempen, <waltje@uwalt.nl.mugnet.org
#
#

# End of hosts.deny.

Look like sshd listen with IPV6 (tcp6) protocol

Did you try to connect with: ssh -6 <your server IP> ?

ACPI: PCI Interrupt 0000:00:03.0[A] -> GSI 31 (level, low) -> IRQ 17
PCI: Setting latency timer of device 0000:00:03.0 to 64
PCI: Setting latency timer of device 0000:00:13.1 to 64
NET: Registered protocol family 2
IP route cache hash table entries: 32768 (order: 5, 131072 bytes)
TCP established hash table entries: 131072 (order: 8, 1572864 bytes)
TCP bind hash table entries: 65536 (order: 7, 524288 bytes)
TCP: Hash tables configured (established 131072 bind 65536)
TCP reno registered
Machine check exception polling timer started.
IA-32 Microcode Update Driver: v1.14a <tigran@aivazian.fsnet.co.uk>
highmem bounce pool size: 64 pages
Total HugeTLB memory allocated, 0
Installing knfsd (copyright (C) 1996 okir@monad.swb.de).
io scheduler noop registered
io scheduler anticipatory registered (default)
io scheduler deadline registered
io scheduler cfq registered
PCI: VIA PCI bridge detected. Disabling DAC.
Boot video device is 0000:01:00.0
PCI: Setting latency timer of device 0000:00:02.0 to 64
assign_interrupt_mode Found MSI capability
Allocate Port Service[0000:00:02.0cie00]
Allocate Port Service[0000:00:02.0cie02]
PCI: Setting latency timer of device 0000:00:03.0 to 64
assign_interrupt_mode Found MSI capability
Allocate Port Service[0000:00:03.0cie00]
Allocate Port Service[0000:00:03.0cie02]
input: Power Button (FF) as /class/input/input0
ACPI: Power Button (FF) [PWRF]
input: Sleep Button (CM) as /class/input/input1
ACPI: Sleep Button (CM) [SLPB]
input: Power Button (CM) as /class/input/input2
ACPI: Power Button (CM) [PWRB]
ACPI: Processor [CPU1] (supports 16 throttling states)
ACPI: Processor [CPU2] (supports 16 throttling states)
ACPI Exception (processor_core-0818): AE_NOT_FOUND, Processor Device is not present [20070126]
ACPI Exception (processor_core-0818): AE_NOT_FOUND, Processor Device is not present [20070126]
Real Time Clock Driver v1.12ac
hpet_resources: 0xfed00000 is busy
Linux agpgart interface v0.102
Serial: 8250/16550 driver $Revision: 1.90 $ 4 ports, IRQ sharing disabled
serial8250: ttyS0 at I/O 0x3f8 (irq = 4) is a 16550A
00:0c: ttyS0 at I/O 0x3f8 (irq = 4) is a 16550A
Floppy drive(s): fd0 is 1.44M
FDC 0 is a post-1991 82077
RAMDISK driver initialized: 16 RAM disks of 4096K size 1024 blocksize
loop: module loaded
Intel(R) PRO/1000 Network Driver - version 7.3.20-k2
Copyright (c) 1999-2006 Intel Corporation.
e100: Intel(R) PRO/100 Network Driver, 3.5.23-k4-NAPI
e100: Copyright(c) 1999-2006 Intel Corporation
Marvell 88E1101: Registered new driver
Marvell 88E1112: Registered new driver
Marvell 88E1111: Registered new driver
Marvell 88E1145: Registered new driver
LXT970: Registered new driver
LXT971: Registered new driver
SMSC LAN83C185: Registered new driver
Broadcom BCM5411: Registered new driver
Broadcom BCM5421: Registered new driver
Broadcom BCM5461: Registered new driver
forcedeth.c: Reverse Engineered nForce ethernet driver. Version 0.60.
8139too Fast Ethernet driver 0.9.28
ACPI: PCI Interrupt 0000:04:04.0[A] -> GSI 17 (level, low) -> IRQ 18
eth0: RealTek RTL8139 at 0xf881ac00, 00:1c:f0:bf:a6:fc, IRQ 18
eth0: Identified 8139 chip type 'RTL-8100B/8139D'
Silan SC92031 PCI Fast Ethernet Adapter driver 2.0c
ACPI: PCI Interrupt 0000:04:05.0[A] -> GSI 19 (level, low) -> IRQ 19
winbond-840.c:v1.01-e (2.4 port) Sep-11-2006 Donald Becker <becker@scyld.com>
http://www.scyld.com/network/drivers.html
uli526x: ULi M5261/M5263 net driver, version 0.9.3 (2005-7-29)
netconsole: not configured, aborting
Uniform Multi-Platform E-IDE driver Revision: 7.00alpha2
ide: Assuming 33MHz system bus speed for PIO modes; override with idebus=xx
VP_IDE: IDE controller at PCI slot 0000:00:0f.1
VP_IDE: chipset revision 7
VP_IDE: not 100% native mode: will probe irqs later
VP_IDE: VIA vt8237s (rev 00) IDE UDMA133 controller on pci0000:00:0f.1
ide0: BM-DMA at 0xfc00-0xfc07, BIOS settings: hdaio, hdbio
ide1: BM-DMA at 0xfc08-0xfc0f, BIOS settings: hdcio, hddio
Probing IDE interface ide0...
Switched to high resolution mode on CPU 1
Switched to high resolution mode on CPU 0
Probing IDE interface ide1...
Probing IDE interface ide0...
Probing IDE interface ide1...
Emulex LightPulse Fibre Channel SCSI driver 8.2.2
Copyright(c) 2004-2007 Emulex. All rights reserved.
3ware Storage Controller device driver for Linux v1.26.02.002.
RocketRAID 3xxx SATA Controller driver v1.0 (060426)
sata_via 0000:00:0f.0: version 2.3
ACPI: PCI Interrupt 0000:00:0f.0[B] -> GSI 21 (level, low) -> IRQ 20
sata_via 0000:00:0f.0: routed to hard irq line 5
scsi0 : sata_via
scsi1 : sata_via
ata1: SATA max UDMA/133 cmd 0x0001dc00 ctl 0x0001d882 bmdma 0x0001d400 irq 20
ata2: SATA max UDMA/133 cmd 0x0001d800 ctl 0x0001d482 bmdma 0x0001d408 irq 20
ata1: SATA link down 1.5 Gbps (SStatus 0 SControl 300)
ata2: SATA link up 1.5 Gbps (SStatus 113 SControl 300)
ata2.00: ATA-7: ST3160815AS, 4.AAB, max UDMA/133
ata2.00: 312581808 sectors, multi 16: LBA48 NCQ (depth 0/32)
ata2.00: configured for UDMA/133
scsi 1:0:0:0: Direct-Access ATA ST3160815AS 4.AA PQ: 0 ANSI: 5
sd 1:0:0:0: [sda] 312581808 512-byte hardware sectors (160042 MB)
sd 1:0:0:0: [sda] Write Protect is off
sd 1:0:0:0: [sda] Mode Sense: 00 3a 00 00
sd 1:0:0:0: [sda] Write cache: enabled, read cache: enabled, doesn't support DPO or FUA
sd 1:0:0:0: [sda] 312581808 512-byte hardware sectors (160042 MB)
sd 1:0:0:0: [sda] Write Protect is off
sd 1:0:0:0: [sda] Mode Sense: 00 3a 00 00
sd 1:0:0:0: [sda] Write cache: enabled, read cache: enabled, doesn't support DPO or FUA
sda: sda1 sda2 sda3 < sda5 >
sd 1:0:0:0: [sda] Attached SCSI disk
sd 1:0:0:0: Attached scsi generic sg0 type 0
Fusion MPT base driver 3.04.05
Copyright (c) 1999-2007 LSI Logic Corporation
Fusion MPT SPI Host driver 3.04.05
ieee1394: raw1394: /dev/raw1394 device initialized
usbmon: debugfs is not available
ACPI: PCI Interrupt 0000:00:10.4[C] -> GSI 21 (level, low) -> IRQ 20
ehci_hcd 0000:00:10.4: EHCI Host Controller
ehci_hcd 0000:00:10.4: new USB bus registered, assigned bus number 1
ehci_hcd 0000:00:10.4: debug port 1
ehci_hcd 0000:00:10.4: irq 20, io mem 0xf9fffc00
ehci_hcd 0000:00:10.4: USB 2.0 started, EHCI 1.00, driver 10 Dec 2004
usb usb1: configuration #1 chosen from 1 choice
hub 1-0:1.0: USB hub found
hub 1-0:1.0: 8 ports detected
ohci_hcd: 2006 August 04 USB 1.1 'Open' Host Controller (OHCI) Driver
USB Universal Host Controller Interface driver v3.0
ACPI: PCI Interrupt 0000:00:10.0[A] -> GSI 20 (level, low) -> IRQ 21
uhci_hcd 0000:00:10.0: UHCI Host Controller
uhci_hcd 0000:00:10.0: new USB bus registered, assigned bus number 2
uhci_hcd 0000:00:10.0: irq 21, io base 0x0000c480
usb usb2: configuration #1 chosen from 1 choice
hub 2-0:1.0: USB hub found
hub 2-0:1.0: 2 ports detected
ACPI: PCI Interrupt 0000:00:10.1[B] -> GSI 22 (level, low) -> IRQ 22
uhci_hcd 0000:00:10.1: UHCI Host Controller
uhci_hcd 0000:00:10.1: new USB bus registered, assigned bus number 3
uhci_hcd 0000:00:10.1: irq 22, io base 0x0000c800
usb usb3: configuration #1 chosen from 1 choice
hub 3-0:1.0: USB hub found
hub 3-0:1.0: 2 ports detected
ACPI: PCI Interrupt 0000:00:10.2[C] -> GSI 21 (level, low) -> IRQ 20
uhci_hcd 0000:00:10.2: UHCI Host Controller
uhci_hcd 0000:00:10.2: new USB bus registered, assigned bus number 4
uhci_hcd 0000:00:10.2: irq 20, io base 0x0000c880
usb usb4: configuration #1 chosen from 1 choice
hub 4-0:1.0: USB hub found
hub 4-0:1.0: 2 ports detected
ACPI: PCI Interrupt 0000:00:10.3[D] -> GSI 23 (level, low) -> IRQ 23
uhci_hcd 0000:00:10.3: UHCI Host Controller
uhci_hcd 0000:00:10.3: new USB bus registered, assigned bus number 5
uhci_hcd 0000:00:10.3: irq 23, io base 0x0000cc00
usb usb5: configuration #1 chosen from 1 choice
hub 5-0:1.0: USB hub found
hub 5-0:1.0: 2 ports detected
usbcore: registered new interface driver usblp
Initializing USB Mass Storage driver...
usbcore: registered new interface driver usb-storage
USB Mass Storage support registered.
PNP: PS/2 Controller [PNP0303:PS2K,PNP0f03:PS2M] at 0x60,0x64 irq 1,12
serio: i8042 KBD port at 0x60,0x64 irq 1
serio: i8042 AUX port at 0x60,0x64 irq 12
mice: PS/2 mouse device common for all mice
input: AT Translated Set 2 keyboard as /class/input/input3
Linux telephony interface: v1.00
ixj driver initialized.
device-mapper: ioctl: 4.11.0-ioctl (2006-10-12) initialised: dm-devel@redhat.com
CAPI Subsystem Rev 1.1.2.8
capi20: Rev 1.1.2.7: started up with major 68 (no middleware)
usbcore: registered new interface driver usbhid
drivers/hid/usbhid/hid-core.c: v2.6:USB HID core driver
oprofile: using timer interrupt.
TCP cubic registered
NET: Registered protocol family 1
NET: Registered protocol family 10
IPv6 over IPv4 tunneling driver
NET: Registered protocol family 17
NET: Registered protocol family 6
NET: Registered protocol family 11
NET: Registered protocol family 3
Using IPI No-Shortcut mode
drivers/rtc/hctosys.c: unable to open rtc device (rtc0)
input: PS/2 Generic Mouse as /class/input/input4
EXT3-fs: INFO: recovery required on readonly filesystem.
EXT3-fs: write access will be enabled during recovery.
kjournald starting. Commit interval 5 seconds
EXT3-fs: sda1: orphan cleanup on readonly fs
ext3_orphan_cleanup: deleting unreferenced inode 16580609
EXT3-fs: sda1: 1 orphan inode deleted
EXT3-fs: recovery complete.
EXT3-fs: mounted filesystem with ordered data mode.
VFS: Mounted root (ext3 filesystem) readonly.
Freeing unused kernel memory: 268k freed
net eth0_rename: device_rename: sysfs_create_symlink failed (-17)
net eth0: device_rename: sysfs_create_symlink failed (-17)
net eth1: device_rename: sysfs_create_symlink failed (-17)
Adding 9807672k swap on /dev/sda2. Priority:-1 extents:1 across:9807672k
EXT3 FS on sda1, internal journal
parport_pc 00:05: reported by Plug and Play ACPI
parport0: PC-style at 0x378 (0x778), irq 7 [PCSPP(,...)]
eth0: link down
ADDRCONF(NETDEV_UP): eth0: link is not ready
eth1: link up, 100Mbps, full-duplex, lpa 0x45E1
eth0: link up, 100Mbps, full-duplex
ADDRCONF(NETDEV_CHANGE): eth0: link becomes ready
Zapata Telephony Interface Registered on major 196
Zaptel Version: 1.4.9.2
Zaptel Echo Canceller: MG2
ztdummy: Trying to load High Resolution Timer
ztdummy: Initialized High Resolution Timer
ztdummy: Starting High Resolution Timer
ztdummy: High Resolution Timer started, good to go
Registered tone zone 0 (United States / North America)
eth1: no IPv6 routers present
eth0: no IPv6 routers present

Net interfaces initialization seems ok, maybe you could try to see what do the log say about ssh,
try (as root): grep ssh /var/log/messages

ran into this problem myself. If it hasnt been answered for you yet which it doesnt look like it is. My problem was that someone had done a eth0 192.168.0.2 with out setting a default gateway so try running these.

netmask 255.255.255.0
route add default gw 192.168.0.1

using w/e IP you would use for your default gateway