I can recreate this. I'm not exactly sure what's going wrong, but there are no udev events for any device past the 16th when you run mkpart with parted.  The reason it does work when you do things to the multipath device is that when the multipath device sends a udev event, the multipath udev rules will make sure the partitions are there.

An easier way to make the device appear is to simply run

# multipath -r [devname]

This will force a reload of the multipath device, which fires off a change udev event and creates the missing partition.

When I run a strace on the parted command, I don't see it even trying to create a 17th partition device, despite the fact that it did write out the partition to disk.

Looking through the parted code, in _dm_reread_part_table(), I see

        int     last = PED_MIN (largest_partnum, 16);

This looks like the root of the problem. reassigning to parted.

What version of parted are you using?

Looks like the change discussed in this thread - http://thread.gmane.org/gmane.comp.gnu.parted.devel/2213 should not have applied to _dm_reread_part_table

Here is a scratch-build that reverts that change, using PED_MAX instead. https://brewweb.devel.redhat.com/taskinfo?taskID=4178996

I've successfully reproduced it on a dm setup on top of a disk image and that fixes the problem.

Making this bug public so others can contribute.

This request was evaluated by Red Hat Product Management for
inclusion in a Red Hat Enterprise Linux release.  Product
Management has requested further review of this request by
Red Hat Engineering, for potential inclusion in a Red Hat
Enterprise Linux release for currently deployed products.
This request is not yet committed for inclusion in a release.

Reproduced with parted-2.1-18.el6, verified with parted-2.1-19.el6:

[root@rtt7 ~]# for i in `seq 1 128`; do start=$((i*20)); end=$((start+19)); parted /dev/mapper/mpatha mkpart primary $start $end; done
...
[root@rtt7 ~]# ls /dev/mapper/
control     mpathap11   mpathap122  mpathap2   mpathap32  mpathap45  mpathap58  mpathap70  mpathap83  mpathap96
mpatha      mpathap110  mpathap123  mpathap20  mpathap33  mpathap46  mpathap59  mpathap71  mpathap84  mpathap97
mpathap1    mpathap111  mpathap124  mpathap21  mpathap34  mpathap47  mpathap6   mpathap72  mpathap85  mpathap98
mpathap10   mpathap112  mpathap125  mpathap22  mpathap35  mpathap48  mpathap60  mpathap73  mpathap86  mpathap99
mpathap100  mpathap113  mpathap126  mpathap23  mpathap36  mpathap49  mpathap61  mpathap74  mpathap87  vg_rtt7-LogVol00
mpathap101  mpathap114  mpathap127  mpathap24  mpathap37  mpathap5   mpathap62  mpathap75  mpathap88  vg_rtt7-LogVol01
mpathap102  mpathap115  mpathap128  mpathap25  mpathap38  mpathap50  mpathap63  mpathap76  mpathap89  vg_rtt7-LogVol02
mpathap103  mpathap116  mpathap13   mpathap26  mpathap39  mpathap51  mpathap64  mpathap77  mpathap9
mpathap104  mpathap117  mpathap14   mpathap27  mpathap4   mpathap52  mpathap65  mpathap78  mpathap90
mpathap105  mpathap118  mpathap15   mpathap28  mpathap40  mpathap53  mpathap66  mpathap79  mpathap91
mpathap106  mpathap119  mpathap16   mpathap29  mpathap41  mpathap54  mpathap67  mpathap8   mpathap92
mpathap107  mpathap12   mpathap17   mpathap3   mpathap42  mpathap55  mpathap68  mpathap80  mpathap93
mpathap108  mpathap120  mpathap18   mpathap30  mpathap43  mpathap56  mpathap69  mpathap81  mpathap94
mpathap109  mpathap121  mpathap19   mpathap31  mpathap44  mpathap57  mpathap7   mpathap82  mpathap95
[root@rtt7 ~]#

Moving to VERIFIED.

Since the problem described in this bug report should be
resolved in a recent advisory, it has been closed with a
resolution of ERRATA.

For information on the advisory, and where to find the updated
files, follow the link below.

If the solution does not work for you, open a new bug report.

http://rhn.redhat.com/errata/RHBA-2013-0407.html