35-36k seems fine for a fight like Ultraxion. Maybe with optimizing your group set-up would allow for a bit of an increase, I find that Ultraxion can be very fluctuating on DPS. Usually I end up somewhere between 37k-41k DPS (this really depends if Doomguard is available at pull).
I've tried the same as you to go demonology on Yor'Sahj, but never thought it was required to go Demo after doing it as Destro. Yes your AoE will be lower, and if your group set-up does not allow for that, then switch to demo. But if you can get away with being Destro, stick with that, because that is the spec you feel most comfortable with.