Sounds like you two aren't in the same party. In online games, whenever people join a game using different consoles, they are automatically assigned to different parties (A, B, etc). You can check and fix this by pushing Start to bring up the settings menu, then R2.
For those who play on the PS3, I am Aereas online. Currently working on the explore 50% of the map trophy, bleh.