Are you sure they weren't there before January? I'm looking at photos off the net of Shibuya crossing (some taking back in 2003-2005) and the marks appear there as well.
For example according to this photo taking in 2003 you can see the red markings on the ground goung around:
http://www.koalie.net/Walks/200311_J...116073344.html
A better outview from 2005 show the lines there
http://hadet.lunarpages.com/me/image...re/tokyo22.JPG
However, I loaded up my Lost in Translation DVD for a quick overview (which was filmed aback in 2002? 2003) and the lines were't there but I saw another picture on the net dated June 2003 with the red markings. So I would say somewhere between 2002-2003 they showed up.