Keep in mind that in the original Dissidia, the villains themselves said that Kuja was the newest warrior of chaos. Also, in the Dissidia Duodecim preview, it heavily implies that he's truly with the good guys, seeing how Kefka tries to provoke Kuja into fighting him, Cloud and Kuja's coversation doesn't sound at all like they see each other as enemies, and he talks to Zidane, Bartz, and Squall the exact same way he talked to Zidane in Shade Impulse 12, where he basically becomes a good guy.