I've given up on building it into the theme as it seems that the plugin I linked to above is doing a brilliant job itself.
Here is the final product ...
Suckerfish WordPress Plugin | Ryan Hellyer
The plugin gives you the ability to control whether the comments are ascending or descending, how many are shown per page and a bunch of other options. Integration with your theme is quite easy too. It took about 5 mins to install, configure and custom integrate with my theme
