I am trying to remove packages using a cloud formation template.
I have and can install it using the both packages and files structures but I need to remove one and install a different version.
i.e. remove java 1.6 and install java 1.4
CloudFormation templates can execute arbitrary userdata scripts, which means you can do most anything you'd like. Here's one sophisticated example, but you could just as easily refer to this puppet guide or the CFN templates page (the highly available RoR template has some nice UserData examples).