I remember that one particular line in sshd_config not being able to have ANY characters (spaces or what not) except for newline after it.

I am not sure if this is still the case but... you never know.

Also, a restart in Ubuntu sometimes is just a config re-load. If that is the case... you might also want to consider a stop then start. This might explain the pseudo open port...

One last item, did you try port 22 when it was supposed to be on the new port? Me thinks it may have answered.