If you bought it from someone else, at least bring in something that shows you bought it, just in case they have any questions. A email confirming the purchase, or a printout of paypal or something- anything to confirm you bought it. I don't think Apple would put you through that much trouble unless the person that sold it stole it.
Here is something else to check. Look at the charge port and see if there is anything pink or red in there. Normally there is a small white tab or window, but if it's pink or red, it's water damaged. Same think inside the headphone port.
If it's water damaged, you have less than a 50/50 shot of getting it replaced or serviced.
Was the phone advertised as jailbroken or unlocked?