I am trying to update the forum name (used in page titles etc) but after changing it in the admin they are still the old titles in the live forum (like they are being cached). I have tried rebuilding all the cache'able parts from the admin but nothing helps.
If the Board Name has been changed in the General Configuration settings, then it should appear as the new name straight away. Settings are saved (and called from, IIRC) ./inc/settings.php. Deleting this file will cause MyBB to automatically create it again using the settings in the ACP.
So, delete ./inc/settings.php and see if it's still happening.
If not, have you tried clearing your browser cache? It may be interfering with it.