Hi Luke,
There are a couple of options. Before I list them please ensure the utag.js file is called just after the beginning body tag. Otherwise the below options will not work.
1) Add a "Javascript" extension scoped to "Pre-Loader" with the Optimizely code. Just load the JS file (e.g.
http://cdn.optimizely.com/js/12345678.js) into Firefox or Chrome and copy/paste the JS code into the extension. This will be initiated as soon as the utag.js file is loaded and run this very high up in the page load process.
2) Move Optimizely to the top of the tags list. Then go to the Advanced Settings of the tag and slide the "Send Wait" slider to "No". Then go to the Configured Publish Settings within Save/Publish modal and enabled "Bundle libs loading on All Pages". All this means instead of the default of running at DOM Ready it will run as soon as the Tealium library is available. This won't run as quickly as the Pre-Loader extension, but will still run before DOM Ready.
Give these a shot and let me know if this helps or if you have any other questions.