With so many problems as of late with the network, the other day I noticed something distrubing. My problems started when I tried to update pre-owned games. My network went crazy, the info bar at the top right stopped scroll information, and I kept getting signed out of PSN. The other night I put Uncharted 2 back in to play and I had no issues whatsoever! Network worked fine, got trophy information, was able to play with no problems. I dunno, call me a cynic, but it looks like Sony is testing their new "device" disallowing pre-owned games to be played on another machine. Coincidence?
Although I do not know what caused your problem, but I do know that it had nothing to do with your game being used. The system is not able to determine if your game is used or not.
Or at least not yet huh chaos!