General :: HTC Sensation Update - Package File Is Invalid

I am seeing an issue on my HTC Sensation when attempting to update Apps that I paid for in the Google Play Store. The exact message that I see when attempting to update these Apps is "Package File is Invalid".

Here is a bit of background to this issue -

1). My HTC Sensation has a custom ROM (Elegancia) installed, and I have now re-installed it (which is when these issues started).

2). I can install a ROM and update Apps through the Play Store just fine at the start

3). I install Titanium Backup and perform a restore (I have tried restoring only data & apps + data [starting from scratch and wiping the phone then installing the ROM again to test both scenarios])

4). Apps return to the state that they were in before I flashed the new ROM

However now whenever I attempt to update Apps I get the infamous "Package File Invalid" message ***

I have noticed when opening Titanium Backup that it alerts me that the "Android ID" has changed, it also gives two options, 1). Leave the new ID, 2). Restore the old ID

5). I tested the updating of Apps both whilst keeping the new "Android ID", and whilst restoring the old "Android ID", the ID (whilst I am sure is important) doesn't seem to affect whether or not Apps will update.

This issue only appears to be affecting Apps that I have purchased, and the Play Store still recognizes that I have purchased the Apps.