This may seem obvious, but is the host actually in the game (as in the two characters done and running around in the game world) at the time you try to invite? Doing it at the main menu or in the character creation panel probably won't work.