"VERTEX" parent type in python not working
For me, your script does not break at the parent_type setting line, but one line later. The parent_vertices array does not expect an object to be given, but an integer: it is the index number of the vertex that needs to be passed on. This slightly modified version of your script works for me in both 2.76 and 2.78:

import bpy

meshobj=bpy.context.object

empt = bpy.data.objects.new("Empty", None)
empt.parent = meshobj
empt.parent_type = 'VERTEX'

# only pass on the index, not the vertex object
empt.parent_vertices[0] = 1

# add the object to the scene so we see what's happening
bpy.context.scene.objects.link(empt)