frame_change_pre handler only works once
As pointed out by zeffi - camera_lens = bpy.data.cameras['Camera'].lens assigns the current value of the camera lens to the variable. That is camera_lens is set to 16.0 when you run the script to insert the handler, this value is then used to set the text every time the handler is run. Only the code within recalculate_text() is run on frame change, not the code before it. What you want is to hold the camera object in a variable and then read the current camera lens setting each time you update the text contents, or to use the full data path within the function.

The off by one issue is the order that things happen. The frame_change_pre handlers are run before frame_current is changed while frame_change_post handlers are run after. frame_current needs to change so that things like a value controlled by an fcurve can be calculated, which allows you to read the keyed value that applies to the current frame.

import bpy

def recalculate_text(scene):
    text_obj = scene.objects['Lens']
    my_camera = bpy.data.cameras['Camera']
    text_obj.data.body = ('{0:.1f} mm' .format(my_camera.lens))

bpy.app.handlers.frame_change_post.append(recalculate_text)