Not sure if this is Majorca wide but my parents are currently staying in Cala Bona and say that on all the Bureau de Change boards there are signs saying that £20 sterling bank notes will not be accepted for change.

Mum had gone with euro's, sterling travellers cheques and English money (just in case) but nowhere, not even their hotel (Alicia) will change £20 notes.

Thought I'd mention it in case someone else does the same and then finds they can't change their money when in resort.