Voltage regulator drop
9V batteries can only source a small amount of current. You are likely exceeding the current that the battery can comfortably source (or, to phrase it differently, you are drawing enough current that the battery's internal resistance causes too large of a voltage drop).

If you measure the battery voltage, you will likely see it dropping below ~8V, which is the drop-out voltage of the LM317 when you are operating it at 5V output. The LM317 may need an input voltage of up to 8V (5V + 3V) to provide a stable 5V output (the recommended Vi-Vo is 3V).

Use several AA batteries in series, or a wall-wart that can supply a decent amount of current.