Be sure to scroll down... there may be more than one question on this page!
Painting over any glued-on coating, whether it is contact paper or wallpaper, is not my first preference. But I "feel your pain" and know that once you start trying to strip it, you are committed to what may be a humongous project!
Contact paper can be painted over but an appropriate primer must be used.
Ordinary oil or latex paints will not stick very well, so a quality
primer-sealer is essential for a long-lasting job and an eminently paintable
surface! One consideration in your choice of primer is its chemical makeup…
you have to be careful not to use a paint that will chemically react with the
plastic or seep into the seams and dissolve the glue! We do not want to make
more work for ourselves! My suggestion is to first use a water-based stain
killing primer, available at any hardware or paint store. These chemical wonders
are designed to stick to virtually any clean surface, giving you that
"eminently paintable surface"! Glass, glossy paints and even plastic
laminate countertops and cabinets are all within its scope!
Be sure to clean the contact paper before painting especially if you think there might be any oil or grease on it. Don't spare the elbow grease… even these special primers will fail if painted over dust, dirt or oils. Use any cleaner you want that is safe for contact paper... just thoroughly rinse and dry the contact paper before priming. Don't under any circumstances use sandpaper to roughen the surface. The abrasions you cause might make the surface visibly rough. You could even tear the contact paper!
NOTE: Since this Q&A was written, Krylon has developed a paint that is designed to adhere to most plastics with minimal surface prep and no priming. It is available in both spray cans and brush-on, though the brush-on version has a smaller color selection.