This is how it is working for me, I'd love to hear if others are doing things differently.
I had the same problem with my 24" ps model. I called HP and was told that you can't use APS to add a new paper to the printer. What you have to do is use the Color Center software to create the profile.
Here's what I've been doing...
Load the paper you want to profile on the printer, and select the closest paper type from the front panel when prompted.
On the PC, start Easy Printer Care. On the Color Center tab click on 'Create and Install ICC Profile'. On the next page, click on the 'Add a new paper' radio button, then click on the Next button. The next page allows you to enter a paper name, and choose the paper type (for some reason, not all paper types are listed - this may have to do with the paper type to selected on the printer).
From this point on you can just follow the prompts to calibrate and profile the paper. Since I'm going to profile the paper with APS anyway, after the calibration is finished, I cancel the procedure and don't profile from within Easy Printer Care. When prompted, I update the paper list in my PC.
This seems to work, but I'm so new at inkjet printing, color management, photoshop, photography, etc that I can't say for sure (I'm doing this as a hobby).
I'd be interested in hearing if what I'm doing is correct!