Quote: "I tried increasing the size of everything"
my guess is that the image was already resized before you started using it which made those edges something other than pure rgb(255,0,255)/magenta. &, increasing the size will only make the edges more obvious.
i'd either manually draw those edges with magenta or select all magenta via the magic wand with enough tolerance to grab those off-color edges, delete then save as a .png image.
either way, you won't be left with the "original" image so, odds are, you'll want to do some touch-up work (or find the original images, wherever they may exist).
Virtual Nomad @ California, USA . DBPro V7.7 . Matrix1Utils 05.27.12
AMD Phenom™ X4 9750 Quad-Core @ 2.4 GHz . 8 GB PC2-6400 RAM
ATI Radeon HD 3650 @ 512 MB . Vista Home Premium 64 Bit