I found out what the problem was. When you book a flight, travelocity often acts only as a middleman in terms of payment processing. In other words, you get charged directly by the airline. Hence, it's the airline who chooses which card to accept (and which not).
While big airlines take all (or most) types of credit cards, small or obscure airlines often have more restrictive rules. Some of them do not accept AmEx. If travelocity acts only as a booking engine in such case and payment processing is done directly by the airline, AmEx doesn't show up as payment option .