Tried it again through another (older) Bluehost account that I administer for an academic association and it does work as planned. This time, though, I started by enabling multi-site. As soon as I added the ‘*’ subdomain, I was able to create new sites. But because I tried creating sites before enabling the wildcard subdomain, I end up with some subdomains I can’t use. No big deal, but a bit unfortunate.
In this case, it’s with the primary (and only) domain for this Bluehost account. But with another account (quite recent), I added the wildcard subdomain to an add-on domain and it seems to work flawlessly. (Mentioned it as a comment here.)
So this might be an unsupported feature Bluehost has. It does support unlimited subdomains and they already do “wildcard redirects.”
The subdomain version does make some things easier, with my existing installation.