I want to say I saw one other person with this issue. I think either setting the Rebellion.user.settings file to start the game in windowed mode or validating the installation fixed his problem.

Sorry for the double post, but I found a solution that worked for me.

Go to: My Documents/My Games/Ironclad Games/Sins of a Solar Empire Rebellion/Setting, and open the 'rebellion.user' file with notepad.

Find the value VideoIsWindowed, change FALSE to TRUE, and start the game. Using the in-game options menu, you can go back and change it to full screen. You should be able to play and start the game in full-screen mode now.