All the advise so far has been pretty good. I'd definitely check the rim diameter, and check to see if you're catching the tube under the bead.
Lots of people use the baby powder trick, but I don't, started without it as a kid, and never really needed it. I also don't put any air in the tube until the tube and tire are all the way on. I've tried it with a little air like most directions say, and I almost always pinch the tube while installing it.
I've also had a couple difficult experiences with both Paselas and folding tires in general. My main bike has Matrix rims that are a bit oversize, so much so that I can usually ride on a flat if I have to without rolling the tire off. But Specialized folding tires wouldn't stay on the rims at anything over 50PSI. I swore off paselas after selling a used bike that had a pair of paselas that looked great. Sold the bike, had everything setup and the tires properly inflated. 100 yards of riding post purchase, and both tires blew out through the sidewalls! The Customer was ok with the free new replacementsI gave him, and I haven't bought or recommended paselas since. I know everyone loves them for the nice supple casings, but I don't think very highly of them at all.
I actually like the cheap tires. The inexpensive IRC or Kenda ones that everyone looks down on.
Steve Birmingham
Lowell, Massachusetts
USA