Is IE8 indicating it doesn't like the cookie ? (If I remember right it's a tiny icon on the bottom, with something resembling an eye or so)
Also make sure to try IE8 in both IE7 and in its IE8 mode.
Microsoft sees P3P as something good, I'm pretty sure they'll still block cookies depending on some settings if you don't have a machine readable privacy statement. [why that would benefit anybody: ask the fanboys]
P3P is in coma if not dead as far as a standard is concerned. But here is the old how-to: [w3.org...]
Alternatively test you can set cookies and send the user to a page telling them how to accept cookies in IE. Might be easier than bothering with P3P, depends on how many are affected.