Scripting -- Can't figure out how to use correct contexts?
I encountered a similar error recently, and thought of adding another solution in addition to the one from @sambler , for the sake of posterity.

The line of code that caused the exception was:

bpy.ops.constraint.followpath_path_animate(constraint='Follow Path')


and, the exception was as follows:

Traceback (most recent call last):
  File "/Users/xxxxxxx/Workspace/blender/moveAlongPath.py", line 30, in &lt;module&gt;
    bpy.ops.constraint.followpath_path_animate(constraint='Follow Path')
  File "/Applications/Blender/blender.app/Contents/MacOS/../Resources/2.76/scripts/modules/bpy/ops.py", line 189, in __call__
    ret = op_call(self.idname_py(), None, kw)
RuntimeError: Operator bpy.ops.constraint.followpath_path_animate.poll() Context missing 'constraint'


Digging into the source code of ops.py that's mentioned in the exception, I ended up at the documentation for bpy.ops and noticed the section on "Overriding Context". The exception's indication of Context missing 'constraint' seemed to ring a bell, and I changed the above line of code to the following:

override={'constraint':mycube.constraints["Follow Path"]}
bpy.ops.constraint.followpath_path_animate(override,constraint='Follow Path')


and, voila! it worked. So, it seemed that somehow the data on the constraint was missing in the context, and injecting the constraint information using the override helped the engine find the constraint where it expected. 

Full working code:

import bpy
import math

"""
blender -b template.blend -P moveAlongPath.py
"""

scene = bpy.data.scenes["Scene"]
mycube = bpy.data.objects["Cube"]

scene.frame_start = 1
scene.frame_end = 100

# Add a nurbs curve
bpy.ops.object.select_all(action = "DESELECT") # Deselect all objects
bpy.ops.curve.primitive_nurbs_circle_add() # Adds a Nurbs Circle and sets it to selected object
bpy.ops.transform.resize(value=(3,3,3)) # Increase the size of the circle
path = bpy.context.selected_objects[0] # Get the currently selected object and get a handle

# Select the cube, and set it to the active object
mycube.select = True
bpy.context.scene.objects.active = mycube

# Add the follow path constraint to the cube, and set target as the Nurbs Circle we just added
mycube.constraints.new('FOLLOW_PATH')
mycube.constraints["Follow Path"].target = path
mycube.constraints["Follow Path"].forward_axis = 'FORWARD_X'
mycube.constraints["Follow Path"].use_curve_follow = True
override={'constraint':mycube.constraints["Follow Path"]}
bpy.ops.constraint.followpath_path_animate(override,constraint='Follow Path')

# Render the animation
scene.render.filepath = "render/anim"
scene.render.image_settings.file_format = "AVI_JPEG"
bpy.ops.wm.save_as_mainfile(filepath="moveAlongPath.blend")
bpy.ops.render.render(animation=True)