Are you in the same lobby channel, and on the same expansion pack?

Are you actually getting to this screen? If you're stopping at a screen with Add Player/Remove Player/Use Player buttons after logging in, that is for creating and using aliases for yourself. You need to add one and use it in order to actually get into the lobby.

What version of the game is everyone playing?

I mean Rebellion, Trinity/Diplomacy, Entrenchment, or the original game (not what patch)?

If you are all playing Diplomacy (Trinity includes that as well as the older Entrenchment and original game), and you're actually getting into the lobby, that covers the common causes of such problems. Please contact support@stardock.com and they should be able to help investigate further.