The feeder roaches are the main reason behind the USDA changes in exotic roaches. I haven't heard that these changes have gone through yet, but they are delisting many of them.
Other than that, yes, it is illegal (without a permit) to own or receive between states any insect that eats any part of any plant (dead or alive plant) and any point in it's life cycle.
Even if the insect is native to both states, you are supposed to have a permit to receive them.
This is for both natives or exotics. If the insect ONLY eats other insects they are, for the most part, ok to own or ship. Also dung beetles are fine.
This has been the same permitting rules and procedures that have been in place since I started working with beetles back in 1999. This is also why I've been trying to get people to comment on the USDA permitting site. Until last year, not much had changed in any way regarding permits for pet insects, and when things had changed - it was for the worse: like when the African Millipedes were taken away (before that, they could be found at almost any pet store). So it's a pretty big deal that they are even considering easing permits -and- that they asked for public comment.
To kind-of back this information up, I have contacts at the USDA/APHIS as well as a majority of the zoos and institutions in the US that exhibit insects. For the past two years I have attended the IECC conference in AZ and sat-in on the "USDA round table" discussion regarding permits. Also, for the past two years, I have been attempting to work with the USDA to ease permits on a specific genus of large, exotic beetle.