Finally managed to get everything working after getting the error below via Software Update:

Strangely enough, when I went to turn off my Mac last night, I was then prompted to either 'Install Update then Shutdown' or just 'Shutdown'. I chose the latter.
Here are the steps that I took before downloading/installing update:
1) Turn off iMac
2) Unplug TimeMachine HD
3) Restart iMac and launch Disk Utility
4) Verify / Repair Macintosh HD
5) Download Lion 10.7.3 Client Combo
6) Install Update and let iMac restart
7) Turn off iMac and plug-in TimeMachine HD
8) Turn on iMac and let TimeMachine do its thing (took about an hour)
Everything ran smoothly and system seems to be woking fine.
EDIT: One strange thing - VLC Player was unselected as my default player for .mkv files on my external HD.
This was easily resolved by right-clicking on movie file, selecting 'Get Info', and changing the Open with application to VLC. Finally I ensured Change All was selected...

Hope this helps
