You could always try a consolidator. www.tiss.com is the one that Travelocity links to, so it may be a good one to use. Depending on your dates, I saw MIA-GIG there for as low 566 USD on Varig and 600 on United. Other dates than the couple I plugged in could be lower or higher. Not quite the fare you saw, but not a killer either.