After a lot of poking, prodding and looking around I found a solution. It isn't elegant but it works.
SOLUTION: MB stores files containing results of the API call to last.fm for similar artists in the C:\Users\**USER**\AppData\Local\MusicBee\InternalCache folder. Each file is named using the following convention - **ARTISTNAME**.similar.dat
In my case, since artists were improperly named, these files were empty. Essentially MB went to last.fm to ask who was similar to America*. Last.fm would respond with an empty result because it didn't know who America with an * was.
When I deleted the * in the artist song tag, AutoDJ still wouldn't work. The reason is that MB didn't make a new request to last.fm for the revised artist name (America). To force MB to make a new request I deleted the existing America.similar.dat file.
The next time I played the song and started AutoDJ, MB looked for the America.similar.dat file. When MB saw the file was missing it made a new request to last.fm and saved the results. After that the AutoDJ worked fine giving a range of similar songs for the updated artist name.
So if you cannot make AutoDJ for a particular artist work you can force a requery of last.fm by deleting the **ARTISTNAME**.similar.dat file.
There is probably a way to force an update from the program rather than manually but I was unable to find it.