@ChunkyMono, I’ve registered to the forum just to thank you for your post. I am a new player (1.5 month) and I had exactly the same problem like you.
I could win Explore level 10, yesterday, and today I was losing at level 2. Sure enough, my casual PVP was on Warlord IV. I have changed it to normal like you said and it solved the problem.
As a new player, I just don’t understand why would difficulty level from PVP had anything to do with Explore difficulty, especially now with new 12 difficulties introduced in patch 4.6? Could somebody explain it to me, please?
Edit: I have found the answer to my question in Patch 4.6 thread: 4.6 Update Patch Notes - #114 by Magnusimus It is a bug.