Im unsure which PS suite your on, but in CS5 there is anew feature called content aware fill. Im no good at PS btw, but give the healing brush tool, spot healing, even lasso tool to make the selection and delete. Worth a try, when i get chance i will give it a go