How can I have Devel generate nodes with different terms and not always the same term?
This happens when you have a default term chosen for the content type. 

If you remove the default, it will then randomly choose terms that already exist (if they exist) or randomly generate terms if the vocabulary allows it.