Default Can't flash custom rom (MDK)

Hi All - Long time listener, first time caller.

I have a Verizon S4 and have been running stock root for a while now. I'm looking to install Carbon ROM. For some reason, when I try to flash it, I get the "Unauthorized Software" message that pops up after it completes and reboots. My only option is to boot back into TWRP and restore from backup. Everything that I've read says that it's because my bootloader isn't unlocked, but I can't figure out how to do it.

Is there something else I need to do? I'm on Ubuntu, so I can't really run the Windows things (unless Odin, for example, works through VIrtualbox? I haven't tried because there are general virtual USB issues that have soft bricked other devices I've had.)

I'm definitely on MDK (I froze the Samsung updater) and my initial effort to root was done on a friend's computer with Odin using these instructions: http://forum.xda-developers.com/show....php?t=2290798.

Running through the forum, I've tried:
http://forum.xda-developers.com/show....php?t=2606501 (Followed the MDK links which go to below)
http://forum.xda-developers.com/show....php?t=2578569 (it just talks about rooting which I already have)

I'm sure there's a step somewhere that I've missed, but I can't see the forest through the trees. Anything obvious that I didn't do?

The only other things I can think of that could get me there:
1. Update to the latest firmware and then just give in and use safestrap (not ideal)
2. Could I re-flash to the pre-release kernel and then go directly to CarbonROM? Will I need to reflash to the release-version of MDK after?

Open to suggestions.