First of all, I will reiterate the various comments that a requirement for Rs of 12 seems a bit excessive.
Nonetheless, if it's a validated method and that's the requirement, then you have to live with it (or revalidate the new method).
Resolution is affected by two things: retention times and peak widths. The retention time for propylparaben meets the specs. Is there a specification for retention time of the product peak? If so, how does that compare with your actual retention time of approx 12 minutes?
If your product retention time matches the specification, then the problem is that your peaks are too wide. If you have run the method successfully on your instrument using the specified (standard) column, then you should check the particle size of the new column. It should be the same or smaller than that of the standard column. If you have never run the standard column on your system, then your problem could be anything: particle size, a defective column, temperature variations, excessive injection volume, excessive dead volume in connecting tubing , etc., etc.
If your product retention time does not match the specification (product elutes earlier than the specification), then you will have to adjust the mobile phase chemistry (probably by tweaking the pH). Depending on how much you tweak (and what your SOPs call for), this may be regarded as a modification to the method (rather than an "adjustment") and may thus require revalidation. C18 columns are not equivalent, regardless of what the USP says! If this were my problem, I would run the method on the originally specified column.