WOW!!! You are good....I have the same stroller and could not get it to fit! The person in Babies R Us warned me too and I still didnt believe her......lol. I have a big carry bag for my stroller with a big shoulder strap......it works great for protection but its kind of bulky. I got it at Buy Buy Baby.....and it was about 30.00. I can even fit extra stuff in it as well so it helps a little with baggage. I guess the extra bulkiness is worth its weight in gold for such an expensive stroller. I used my Graco metrolite on my last trip and Southwest broke a piece off of it! Thank goodness the piece is replaceable!
Have a great time on your trip!