Your code fragment is missing two things:
- How you set the
scene
variable. I'll assume you wanted the active scene and use
scene = bpy.context.scene
- How you set the
track_object
variable. I'll assume you wanted the active object and use
track_object = bpy.context.active_object
With those two changes, your code looks like
import bpy
track_object = bpy.context.active_object
scene = bpy.context.scene
cam_data = bpy.data.cameras.new('camera')
cam = bpy.data.objects.new('camera', cam_data)
bpy.context.collection.objects.link(cam)
cons = cam.constraints.new(type='TRACK_TO')
cons.target = track_object
scene.camera = cam
and when I run it it creates a camera with a Track To constraint set to point at the active object in the scene I created.

When I later execute
cons.target = bpy.data.objects["Suzanne"]
and I have a Monkey in the scene, the Track-To target changes to the Monkey.
So your problem seems to be that you haven't set track_object
to the object you want as the target.
EDIT:
Here is a Blend file with a cube and a monkey. I've modified the code to use the cube rather than the active object as the first target of the track to, but you can double check my work. It's a 3.0.1 file, but should work just fine in any Blender version since 2.8

target
? $\endgroup$target_object
. Are you sure it's set to the right object? $\endgroup$