I disagree with the thinking that 2 platys can't be kept in a 5 gallon. They can, but you have to keep up on the tank. I have had 6 neons in a five gallon for over two years at my desk at work.
Try for either two males, or two females... and yes, keep up on the water changes, use Prime as your water conditioner, and see if the LFS will give you a small cup of gravel (put it in a bag, and set it in the filter, to introduce the nitrifying bacteria.)
Other than that, just have patience. They will do fine in the small tank, if everything else is kept up. There aren't many fish tougher than platys either, which is why many fish shops recommend them.