Aaron generously contacted me off-list and helped me troubleshoot the problem, which turned out to be that our virtual machines were in the "all VM computers" group, but not in the "allComputers" group.
I'm still not sure what that mattered for Shib-backed accounts and not for local ones, but adding them to the allComputers group fixed the problem. Shib-backed users can see and deploy images to VM's now.
