Most photo editing software has a way to select the background (like the lasso tool) - a lot of times you select what you want to stay the same, then do a 'select inverse'. Then you can modify the background's color or whatever you need to do. The trick there is getting the right sections selected so the people in the photograph don't get modified too.
If you are use to cutting out photos for scrapbooks etc though - the printing, cutting, rescanning option might be the quickest
Unfortunately I just setup a new computer and don't actually have Photoshop Elements installed anymore, so I don't remember what the menus etc are called, but there should be an option to change colors or hues. I do remember the hard part was getting the selection right - though it'd be the same issue with scissors - you don't want to cut out too much or too little.
Good luck