To my knowledge, both are correct, the difference is very slight between which word will be the adjective of the other :
islamiyyiina who are mutashaddidiina
or mutashaddidina who are islamiyyiina
It's mainly because both words are/can be used as adjectives.
Yeah, that makes sense. I don't know why I was having so much trouble with that. As I was thinking of both possible structures in my mind I could not see why one was better than the other. I can see how either one would be good as both can be used as adjectives.