Your Bing Lock Screen will update at a certain point of the day in my experience. It will also 'fetch' new lockscreens for the next few days whenever you've got a data connection or WiFi connection.
Any ideas if there are any apps required to run in the background? I recently tried using the Bing lockscreen on a 920 and 730 and neither of them update. On both phones I don't allow much to run in the background, Cortana included.