In a message dated 8/6/2013 1:23:47 P.M. Eastern Daylight Time, writes:

here is the Berliner Puzzle Plate, January 21, 1901. I'm not sure if this
is the first one, but it shows the use of the name Puzzle since 1901.
-------------
 According to my notes, this particular Puzzle Plate - the second one
issued by Berliner (#9317/8) - was recorded on Jan 19, 1901. I think there were
three versions, which may account for the slightly later date given here
(Jan 21).
 
  His first Puzzle Plate (2 piano solos) was #5504, in late 1898
(England). See PHP for more details.
 
Allen