After Otto's awesome observation, some SQL trickery I believe I have now fixed the problem :)
@Otto - if you post an answer post with your observation with the comment, I would be more than happy to accept it as the answer
The Problem
I was using tumblr and transferred my posts to WordPress. However, since approx mid-Dec tumblr postIDs were greater than 32-bit MAX_INT (2147483647). Of course, I had several posts created after mid-Dec, thus they all had postIDs greater than MAX_INT - http://wordpress.org/support/topic/plugin-wordpress-importer-importer-fails-for-post_ids-over-php_int_max-of-2147483647
For whatever reason, my posts imported fine, however the WordPress Stats did not like these insanely large numbered postIDs, thus I experienced the problem outlined in my question.
The Fix
WARNING!!!
Fiddling around with postIDs/database can potentially screw up your blog - linking etc. So perform at your own risk!
I was very lucky that this was a fairly new blog - 0 comments and only 18 posts... so overall it was still fairly simple.
Remember to back up, incase something horrible goes wrong!
To solve this problem, I backed up WordPress, cleaned up my WordPress database, exported all tables that had references to postIDs, reduced the postID values, reset the auto-increment value, re-inserted the data.
Backing up: I did an XML export and also performed a full backup of the blog via cPanel.
Cleanup database: There was a useless rows (for post revisions) in the database, so to simplify the later steps I first cleaned up my database using the following plugin: http://wordpress.org/extend/plugins/wp-cleanup/
Export tables: Going into phpAdmin through cPanel, I went through each table and any that had references to postIDs I exported into a .sql file, remember to include the drop tables if exists option. The tables I ended up needing to export were: wp_posts, wp_postmeta, wp_term_relationships. !!! NOTE: I was lucky that this is a relatively new blog. So there were 0 comments, thus did not need to worry about comments!!!
Reducing postIDs: Using numbers (ie. excel) I first made a mapping of the old/new postIDs. (eg: 2165214909->3, 2165214895->4 etc). With the old/new postIDs 'set', I went through each of the exported .sql files and did find/replace all. Note: it appears that attachments in posts also have their own postID so it can be a tad confusing
Reset auto-increment number: In the wp_post.sql file, I reset the auto-increment value to something like 30. That way the next blog will have a postID starting at 30. If you don't reset this, any new posts created will still have high postIDs and you'll be faced with the same problem.
Re-inserting data: Back in phpAdmin, using the .sql files containing the new postIDs I imported the data back in. Since in the export I chose to drop table if it exists, it cleared the existing tables and inserted with the "new" data.
After doing all of this, I did a quick sanity check to make sure everything was fine. Public blog - clicked around, made sure images were there, searching works, tags worked etc. Admin section - check that when you hover over 'Edit' it shows the correct new postID, creating a new post uses the new auto-increment id, and of course (after a few days) that the WordPress stats was back to normal.
All checks passed, so I think the fix has worked :)