I can't see how the speed sensor could cause it to be out a bit, it's just a pulsed signal, a dodgy sensor couldn't change the timing of the pulses it sends. It might miss pulses or stop them all together, but that'd cause the speedo to stop or under-read, not over-read. Still worth checking out though, it's quite simple and all just unclips with no tools if I remember right. It's on top of the diff and on a 1.8t (and maybe others) it's covered with a little heat shield pocket.
It does sound quite likely that the tyre size is out. What actual size are they? Seems odd though, being that far out they'd be quite noticeably visually smaller. Still there's a lot of room for error with a small wheel and big tyre.