I've been taking a look at this today, and the following is happening:
1) RHEL-4 and RHEL-5 parted will only notify the kernel about the first 16 new partitions
2) But the blkpg ioctl used by parted to notify the kernel about new partitions only works for up to 15 partitions, so this fails at the 16th partition (this is the error msg seen)
3) When the notification of the 16th partition fails, RHEL-4 parted gives up, where as if cancel is chosen up on the error msg (*), RHEL-5 parted switches to using the BLKRRPART ioctl, including sleeping and retrying a couple of times. This will happen once per partition being added over number 16, which adds up to the large delay seen.
Note that unless a second error message with this text:
_("The kernel was unable to re-read the partition "
"table on %s (%s). This means Linux won't know "
"anything about the modifications you made "
"until you reboot. You should reboot your computer "
"before doing anything with %s."),
Also shows up, the kernel is actually successfully notified of the changes, as the retry done by the RHEL-5 parted then has succeeded.
A possible fix for the false printing of the error message is to not even try to use blkpg when there are more then 15 partitions on the disk.
*) Note that cancel is automatically chosen when running in script mode.