Well, our new line following robot is done. With any engineering project, you can always do more, but after tidying up the program, and tweaking values for a few hours, we came up with a reasonable configuration, able to complete out test circuit in an average of 40 seconds.
The robot is much quicker making left turns than right turns (as shown in the video below). When the robot looses the line, it will turn left to try and find it. If the path leads left, the robot will find the line again very quickly, and continue. If the path leads right, the robot will try to seek left, fail to find the line within a pre-determined time, then seek left to find the line.
The following images show a summary of the program, as shown by the graphical programming environment supplied with the NXT.

The main body of the Bilby’s program

The section of the Bilby’s program that instructs it to seek left

The section of the Bilby’s program that instructs it to seek right
For those unfamiliar with reading NXT programs, here is a pseudo-code version:
Wait until sensor sees black
loop forever:
move forward
wait until sensor sees white
call seek_left
if sensor sees white:
call seek_right
seek_left:
loop 10 times:
pivot left (move left motor backwards, and right motor forwards)
if sensor sees white:
wait 0.01 seconds
seek_right:
pivot right (move right motor backwards, and left motor forwards)
wait until sensor sees black
wait 0.02 seconds
All in all, not bad for a few hours tinkering, we certainly enjoyed it. For those interested in seeing more, we recorded a video of the robot in action, and are also providing the program we used.
Download Video (2.95Mb, slow connection, 109secs)
Download Program (339Kb)