Sometimes MSMQ hates you. Like when you reboot your dev instance of NPM and the MSMQ fails. A quick call to SW support was met with a 'It's a Microsoft service and we don't support it'. What the heck?! Doesn't NPM and SAM (and maybe other modules) enabled MSMQ during the install process.
So I went digging for a solution myself and here is what I found.
You'll find that event ID kicking around the application event logs on your server. It will say something like:
The Message Queuing service cannot start. The checkpoint files cannot be recovered. To start the Message Queuing service without losing consistency, you must correct or recover corrupted checkpoint and log files. To start the service for emergency use (with a potential loss of data consistency), delete the files QMLog, MQTrans.lg1, MQTrans.lg2, MQInSeqs.lg1, and MQInSeqs.lg2 from the Msmq\Storage folder and add the DWORD registry key HKLM\Software\Microsoft\MSMQ\Parameters\LogDataCreated with a value of 0. Error 0xc00e03f1:
Follow the steps in the link above and, tada, MSMQ services will start right up. You can then start all of the other, dependent, Solarwinds services.
Take that Windows Server!