I had issues with private matches with my buddy. We both powered off/on and then had no issues from there.
Darkfwank the same thing has happened to me with two buddies it was really weird every time we tried to connect it would say game session is no longer available but when we dashboarded it and went back into the game it worked and with both of my friends i was in there xbl party.