For anyone who reads the above post in the future I resolved the issue by doing the following:
1. Logged into QA complete.
2. Navigated to the Automation section and selected option to 'Delete Host' to remove the currently configured host.
3. Re-installed Test Execute and Software Testing Bridge on my testing machine.
4. Edited the software testing bridge config files as per the bridge documentation.
5. Configured web service address and login details in the software testing bridge.
6. Loaded our test project in the software testing bridge and pointed it at the top level directory for our Test Complete project files.
7. Re-started the testing machine.
8. Scheduled an automated test run in QA Complete.
