I am having this problem also and would be interested in knowing the solution. The only way I've found to get a new image is to change to a static image then switch back to the bing image.
Got a Verizon HTC 8x doing the same thing. Setup the Bing lockscreen option in settings and the image does not update unless I change the app to a different one and come back to bing... this sux.