Thanks for the reply.
I've tried what you said, but from the FC6 box itself ("telnet localhost 5900" & "telnet localhost 5901"). I don't see how doing this from any other machine outside my local network would help, as I'm tunneling the VNC connection through ssh on port 443, not just using a plain VNC connection through port 5900 (or 5901) through my router.
telnet: socket: Address family not supported by protocol
telnet: Unable to connect to remote host: Illegal seek
The only changes I have made to this box is the IP address change, and a "yum upgrade" now and again. I'm still convinced it's something to with either of those things, as this was working perfectly before that and nothing at the client end has changed.
Any more help on this would be greatly appreciated, as I'm a bit limited by being stuck to the command line at the moment.