Lost passwordless sudo and no root access
Solution 1:
Can't say for sure why it happened. If your sudo rule was based on your user being part of a specific group (e.g. wheel or sudo) and you were removed from that group that would explain it.
You shouldn't need to blow your instance away, but you will need to stop it (not terminate) and attach the disk to another instance where you have root access so it can be fixed. More information from Amazon's website