Here's what fixed the issue for me.
Steps:
Start > type 'regedit'
Navigate to HKEY_CURRENT_USER\Software\Microsoft\Office\Excel\Addins
Then change the value of loadBehaviour to 3 for HyperionComAddin. As shown below. Just to clarify, this is the add-in that was not loading during start up for me. Picture in the question is to give an example.
Close registry and reopen it to make sure that value has not changed.