Hi,
it definitely looks like mine problem which I tried to solve few weeks ago. Its good to know that version with level shifter is probably extremely (not "just") recommended (even these are really few % of market).
Thats why I have ordered shield from ebay which has level shifter IC. Also it has ICSP header, so it could be used on Mega an also on Uno. I am using Mega2560.
It will arrive in next days (I hope), and it costs under 10$ with shipping 
I may post a link of that if you want...