Well, if you're doing the change for leveling in cataclysm. Don't do the rogue leather. Remember the thing about wanting to wear the plate armor for the plate benefits?

And I suspect with the polearm, it's an issue of "does it hit harder than the one you have?"

If so, then yea, give it a shot. But, I'd still trump with strength. And that's the thing with the leather, does the AP on the rogue leather, get you the same 2.3AP from a strength item in the same slot?

It's not that it's just agility, it's the overall itemization. Leather has less stamina (and therefore more item points for dps stats), and dps paladins like crit. Agility gives you crit, and it scales with raid buffs and blessing of kings. Leather items are more likely to give you more crit and haste.

Compare the BiS pally belt:
http://www.wowhead.com/item=50067

v. a very good plate belt you can get for emblems:
http://www.wowhead.com/item=50987

While the critical strike on the plate belt looks better at first, the +104 agility gives you a full 2% critical strike rating. The leather belt gives you almost a full 4% crit from ONE item, and that only goes up with Blessing of Kings. And while armor penetration is suboptimal for Paladins, it's still a stat that will increase your dps through physical strikes. And once you get a proc-based weapon like Bryntroll or a proc-based trinket like Tiny Abomination in a Jar, haste starts also scaling amazingly well.

So basically, for paladins, it's the combination of all the DPS stats that is on leather without being hamstrung by extra stamina and armor that makes some leather items Best in Slot.

Speaking of leather, if one does have plenty of gold or whatever and is getting some craftables, I would wait a bit on getting the i264 boots until you see what the rest of your kit looks like, because with the rest of your gear eventally, the Leather ones (http://www.wowhead.com/item=49895) may be a better choice. Or you could just assume they will be and get those instead.
I would also caution against getting the plate i264 pants crafted because you WILL be using the t10 ones eventually as part of your 4pc. The gloves are the one piece of the tier set rets eventually drop/replace, but since the 2 pc bonus is critical to get ASAP and the shoulders/gloves are the cheapest to get frostie-wise, unless you get lucky on VoA drops you will probably purchase those 2 first.
Do NOT buy anything else with your frosties until you have your tier 10 set.
I'm sure that will be covered in the 3rd part but I just wanted to get that out there ;-)

Aloix is right, uprate that man. Here is one other suggestion though:

You can "borrow" the Herkuml War Token, if you have, say 75 emblems of frost and are not ready to get your helm/chest or whatever. Spend the 60 frost emblems for the trinket, use it for less than 2 hours, then go sell it back to the vendor for your 60 frosties. Then buy it right back so you can "borrow" it for another 2 hours if you need. (This works great for any trinket, for any class and spec.)

Paladins currently have the best agility-to-crit conversion of any physical DPS class; for whatever reason, it's a little better than what warriors and DKs get, and all the others had their agility:crit ratios nerfed to keep them from scaling too well with agility, since it was going to be stacked for the AP anyway. Point-for-point, a paladin does still prefer crit rating to agility, but it's close; something like 49.something crit rating = 1% crit = 52 agi.

Question: won't Leather become less attractive in Cata because all the AP will become Agi?

One thing to remember is that while AGI does scale with Kings, the Crit Strike rating we gain from AGI is melee-only. +Crit applies to both melee and spell, and while spell crit isn't really that important to ret, it is helpful for spot heals (Flash of Light) and Exorcism.

Jbodar: It sure looks that way.