It can't be the internet connection though, the computer version of the game runs fine with no lag.
Those of you with PS3's with no noticeable lag, what size HDD do you have for it? The one I have right now is almost full, I'm about to swap it for a fresh 500GB one (non-SSD unfortunately) and it didn't occur to me until now that the lack of space might be the culprit.
BTW I know the HDMI connection isn't going to cause that lag, I only mentioned it because the guide had specific tips on that type of connection.