Scam
Sounds like a scam to me. I've flown over Sao Tome and Principe many times over the years and this has never happened. Usually I have paid nav fees enroute to the appropriate people (usually ASECNA for this region).
Does your flight match the dates they gave?