Changing port hangs sshd

[Mauriat Miranda]

Hello,

I have a remote virtualized fedora core 2 server, which I have access
by SSH and a web based control panel. I was being bombarded by brute
force SSH attacks on port 22, so I moved sshd to run on a higher port
- which ended the attacks.

The change did not take effect when I restarted the sshd service, but
did when I rebooted the entire server. I was able to use ssh at the
higher port for a few hours but when I came back a day later
connecting with ssh would timeout. However all my web based tools
indicate sshd is still running without problems.

Restarting the sshd service doesn't seem to have any effect.
Rebooting the server fixes the problem, but again only for a few hours.

I have tried multiple different ports.
I have the the basic set of apps (apache, mysql, mail, etc.).
I'm not running iptables.
There are some extra tools such as 'portsentry' running, but most of
them are idle or using blank defaults.

I'm using openssh and I changed the port via /etc/ssh/sshd_config
The server is updated with the last set of FC2 security updates.

How would I go about trying to fix this? Running 'ssh -vvv' verbose on
the client end doesn't reveal anything. And my server logs don't
indicate any sort of problem either.

Does anybody have any idea or hints? Seen something like this before?
Am I missing something critical (obvious)?

Any help is appreciated.

Mauriat