I followed the KB article and verified that all the settings were already correct. The new location is reflected already. Something I noticed is that I can create a brand new Storage group, and within that, I can create a new Mailbox store.
UPDATE - I did figure out what the deal was. There were some old log files in the default directory that hosted the the First Storage Group. After I moved those to a different directory, I was able to mount the mailbox stores and create empty databases. As it turns out, it appears that one of the other administrators may have attempted to resurrect the mailbox store before I was in there (hence the bad logs). Thanks for your help.