So, to update this bug report the SystemD init system periodically tried to start up the "snap.canonical-livepatch.canonical-livepatchd.service" and at some point around Feb 24th, 21:53 UTC time, it started working:
Code:

Feb 24 03:03:56 ip-10-0-16-09 /usr/bin/snap[5967]: cmd.go:111: DEBUG: restarting into "/snap/core/current/usr/bin/snap"
Feb 24 03:03:56 ip-10-0-16-09 snap[5967]: 2017/02/24 03:03:56 Only Ubuntu 16.04 LTS is supported, exiting.
Feb 24 03:03:56 ip-10-0-16-09 systemd[1]: snap.canonical-livepatch.canonical-livepatchd.service: Main process exited, code=exited, status=1/FAILURE
Feb 24 03:03:56 ip-10-0-16-09 systemd[1]: snap.canonical-livepatch.canonical-livepatchd.service: Unit entered failed state.
Feb 24 03:03:56 ip-10-0-16-09 systemd[1]: snap.canonical-livepatch.canonical-livepatchd.service: Failed with result 'exit-code'.
Feb 24 03:03:57 ip-10-0-16-09 systemd[1]: snap.canonical-livepatch.canonical-livepatchd.service: Service hold-off time over, scheduling restart.
Feb 24 03:03:57 ip-10-0-16-09 systemd[1]: Stopped Service for snap application canonical-livepatch.canonical-livepatchd.
Feb 24 03:03:57 ip-10-0-16-09 systemd[1]: snap.canonical-livepatch.canonical-livepatchd.service: Start request repeated too quickly.
Feb 24 03:03:57 ip-10-0-16-09 systemd[1]: Failed to start Service for snap application canonical-livepatch.canonical-livepatchd.
Feb 24 21:53:50 ip-10-0-16-09 systemd[1]: Stopped Service for snap application canonical-livepatch.canonical-livepatchd.
Feb 24 21:53:51 ip-10-0-16-09 systemd[1]: Started Service for snap application canonical-livepatch.canonical-livepatchd.
Feb 24 21:53:51 ip-10-0-16-09 /usr/bin/snap[13457]: cmd.go:111: DEBUG: restarting into "/snap/core/current/usr/bin/snap"
Feb 24 21:53:52 ip-10-0-16-09 snap[13457]: 2017/02/24 21:53:52 open /var/snap/canonical-livepatch/common/config: no such file or directory
Feb 24 21:53:52 ip-10-0-16-09 canonical-livepatch[13457]: Starting client version 7.21
Feb 24 21:53:52 ip-10-0-16-09 canonical-livepatch[13457]: No machine-token. Please run 'canonical-livepatch enable'!
Feb 24 21:53:52 ip-10-0-16-09 canonical-livepatch[13457]: No payload available.

I have NFI what caused it to start working, neither the apt history or "snap changes" show anything being updated around that time:
Code:

root@ip-10-0-16-09:~# snap changes
ID   Status  Spawn                 Ready                 Summary
10   Done    2017-02-26T03:03:49Z  2017-02-26T03:03:49Z  Refresh all snaps: no updates
11   Done    2017-02-26T06:14:13Z  2017-02-26T06:14:13Z  Refresh all snaps: no updates
12   Done    2017-02-26T13:01:39Z  2017-02-26T13:01:39Z  Refresh all snaps: no updates
13   Done    2017-02-26T19:58:29Z  2017-02-26T19:58:29Z  Refresh all snaps: no updates
14   Done    2017-02-27T00:53:39Z  2017-02-27T00:53:39Z  Refresh all snaps: no updates

Once the service was running, I was able to validate the key using the "canonical-livepatch enable ...." command and everything is working as expected.

It's still a bit of a mystery as to what caused it to start working. Maybe something changed server side on the Ubuntu Livepatch servers? Maybe there was some kind of "cached" OS version value that needed to be cleared?

Either way, will update the bug ticket and this thread can (probably?) be marked as resolved, though the resolution is basically "wait and it'll come right".