Widebody; Low Wing; 2 Turbojet Eng
Flight Crew Air Transport Pilot (ATP)
Communication Breakdown
ATC Issue All Types; Deviation / Discrepancy - Procedural Clearance; Deviation / Discrepancy - Procedural Published Material / Policy
Air Traffic Control Issued New Clearance; Air Traffic Control Provided Assistance
Human Factors; Procedure
Scheduled to depart ZZZ. A new Nav database was valid. As we were not sure which database to use we consulted the Flight Manual which stated that the database changed; and if that was during the flight we could elect either database; but we would have to verify everything for the time the database was outdated. As we were arriving right after this time we elected to use the old database. We only received a partial route uplink. We consulted with dispatch and they stated that the new database was effective and there were new airways through Brazil. So we switched to the new database. We then were able to load the full clearance. We were cleared as filed. Enroute [ATC] asked our route and informed us that the airways and waypoints we were filed on didn't exist. Further; they attempted to clear us to waypoints that we no longer had in our database. We were finally able to get a clearance to a waypoint that was at the end of Brazilian airspace; and we had no problems after that. I submitted a [report] asking if the FOM the Brazilian controllers [were using] were correct; or if dispatch was correct concerning the time the new database was effective.
Air carrier First Officer reported database update issues while transiting through Brazilian airspace. Crew were cleared to waypoints not in the updated database.