There is really nothing we can do for you. First of all, you need to tell us the correct iPhone model you have. Pick from the ones listed below:
iPhone
iPhone 3G
iPhone 3GS
iPhone 4
iPhone 4S
iPhone 5
iPhone 5C
iPhone 5S
If you just bought it new like you said you did, take it back to the place you purchased it from and exchange it for a different one, especially being that your own wireless carrier couldn't assist you. Simply explain the situation to them. If you live near an Apple Store, take it to it for the best results. With that in mind, you can try one other thing if you have a computer that is connected to the internet, and that is put your device in DFU mode, connect it to your computer, initiate the computer's iTunes app (hopefully, the latest version), and when iTunes detect that your device is in recovery, select to restore and update it.