With the data you provided, but without taking into account any connections or self-transfers, and making up dates, I checked the public portals of Timatic (the IATA Travel Centre) and TravelDoc. Some airlines use Timatic, others use Traveldoc. Even at those using Traveldoc agents may still say they checked on Timatic.
The IATA Travel Centre is a but confusing: it says "yes, no, but":
So: Yes, it's all fine. No, you need a visa. But you can get a visa on arrival.
Traveldoc says "no, but":
So: No, you need another document, but that other document is either a hotel booking, or proof of means, or "a pre-approved visa sponsorship via Maldives Immigration". It does not mention visa on arrival though.
It's a bit confusing (and it may be presented differently to the agent, depending on the airline and/or airport), but any well trained agent should be able to understand what it actually means.
Note that Timatic will say nearly exactly the same thing for other nationalities: still "Yes, No, But", and they actually show more conditions than for stateless persons.
Traveldoc gives a different result with another nationality (e.g. Canadian): it does not say "no, but", it says "Please check the messages below to see if travel is permitted." and "Visa may be obtained on arrival in Maldives. Maximum stay of 30 days.".
Note that I used dates (for the travel and for expiry of the documents) which I know fulfil other requirements. The full requirements state:
Tourist Visa
Tourist visa is granted for all nationalities on arrival to the Maldives. As such, a foreigner travelling to Maldives as a tourist does not require pre-approval for the visa. However, the person must satisfy the basic entry requirements to get immigration clearance upon arrival.
The basic entry requirements are as follows;
- A passport or a travel document with Machine Readable Zone (MRZ) with at least 1 month validity. (Passengers with an extended validity in their passports are not allowed to enter.)
- A complete travel itinerary including return journey confirmed tickets, with a prepaid confirmed hotel booking at a registered hotel, and provide proof of financial means for sufficient funds to support the stay in Maldives, or hold a pre-approved visa sponsorship approved by Maldives Immigration.
- Entry requirements to their onward destinations; for example, the visa and passport validity.
- Traveller Declaration must be filled in and submitted by all travelers travelling to and from Maldives, within 96 hours to the flight time. The form has to be submitted electronically via IMUGA.
- Yellow Fever Vaccination Certificate, if applicable. Children under 1 year of age are exempt from Yellow Fever vaccination. Click here to check the Yellow Fever endemic countries.
So some of the possibilities are (in no particular order):
- Your travel document does not fulfil the requirements (extended validity, less than 1 month validity, no MRZ...)
- You did not have a return ticket or the return ticket was more than 30 days after arrival
- You did not have a prepaid confirmed hotel booking at a registered hotel (or one of the alternatives, though note that the official wording says A and B or C, while TravelDoc apparently says A or B or C)
- You had not completed the Traveller Declaration online (though I'm not even sure in the case of the Maldives they would be able to check that at the origin)
- Your trip involved a transit somewhere (I'm not aware of direct flights from Canada to the Maldives), and that's were the problem was (especially if that transit is a self-transfer rather than a single-ticket through connection)
- The agent just didn't understand the rules as stated on TravelDoc (where they are probably most confusing) or Timatic, or incorrectly entered your data.
