It seems I managed to find a solution to my little kernel panic problem after all. A bit of background for context...

After doing a fresh install of Ubuntu on my hardware, I was getting a blip of error text prior to the login screen appearing. Most of it referred to an "ACPI exception" error (which I still need to research, but is probably unrelated to this thread), but the second to last line stated:
AMD-VI: Unable to write to IOMMU perf counter.
I was just ignoring this error text because as long as I wasn't plugged into the 580, everything booted ok.

Now, doing a bit of searching on AMD's support forum for open-source AMD topics, someone mentioned (and I lost the URL, sorry) that there have been issues with memory management in Linux with AMD GPUs, and that by turning off the IOMMU on startup, that solved the problem for them (they were getting black screens instead of kernel panic text). So, I changed my grub config like so:

GRUB_CMDLINE_LINUX_DEFAULT="open splash iommu=soft"
...and voila! I was able to boot to the desktop on my 580 !