Try checking out the travel agency.
Show them the proof they need to get the ticket.
Take out the letter that you start the game with and show it to them.