In reply to 1234None:
Hey Dave,
I went to Tioman back in 99, so thinking my info isn't really up-to-date ! I got the coach over, Malaysian coach service is excellent. Just rock up to Puduraya bus terminal and you can book anytime. Buses are very frequent.
There's some good guest houses at mersing.
I'll bung you a message with a friends email who went there last year (she's not a climber)
Chris