Does my garden brickwork need mortar?
I think you may have a problem brewing there.  I have never heard of bricks being glued in a situation like this.  Normally paving bricks will be set on a compacted base of stone dust and very fine packing gravel, then the joints are filled with fine mason sand.  Mortar is rarely used, especially in cold climates as it will crack with any movement associated with freezing or heaving. 

If your bricks are moving under your feet, then they were not seated properly or the base is not properly leveled or compacted.  It is not acceptable to have any movement in the field from foot traffic. If your contractor says that is normal, or won't come back to fix the problem, You have a problem. The glue comment throws me. If your contractor said he "glued" the bricks in place, then I think you may have hired the wrong contractor. Maybe he specializes in hanging wallpaper!