Hmm... I can see offhand how to deal with it if L/K is Galois, but I'd have to think about it otherwise... In the Galois case, above p you have r many prime ideals, each with ramification index e, and residue degree f. The rough sketch is to view this as a problem about discrete valuations, rather than prime ideals.
N(P) (according to your second definition) = < N(a)| a in P >. We know this is an ideal in O_K, and it only remains to describe its decomposition into primes. Since the ramification index of p in (each) P above it is e, the minimal p-adic valuation of an element in N(P) is f. So if t is a parametrizing element of the p-adic valuation (choose it in O_K), then u*tf*rf generates N(P)p where u is in O_K - P (check that N(P) isn't divisible by other prime ideals, with similar methods).
Hope that helps a bit with the intuition.
After reading Adam's solution, I noticed a few things were wrong in my argument. They were corrected in the body.
