If your game has been updated you shouldn't be having the same problem. Were you getting an error code when trying to reconnect?
Did you try hosting?
Try playing at different times of the day. Basically, check off-peak hours for your ISPs, in case there are any issues with congestion or throttling, etc, on evenings or weekends.
Did you both double check your game / Xbox / router / modem settings?
