I would agree it's most likely the paint. About 1 year ago we installed some Avery low tac wall material on a painted wall, semi gloss finish, 2 weeks later customer called some of the letters were curling off the wall. Since the job was 30 miles down the road I printed more vinyl and cut new lettering. I replaced about 6 or 6" letter that were curlin on the edge. I had use Avery as it is the only one I know of that advertises you can prin to the edge and cut, the customer had specified a pantone color and wanted removable vinyl. I took the curled letters back to my shop and install them on our wall, they are still there, no curl a year latter.
I also had a similar problem about 20 years ago with hi performance vinyl on a customer painted wood surface. We lettered the wood the customer picked it up in a pick-up truck and by the time he got to his destination most of the lettering had blown off. Some easy clean scrubbable paints have additives that will not allow adhesive to stick.