With new ATmega328P chips, you need to do a Tools > Burn Bootloader before you can upload to them. The exception is if you bought ATmega328P chips which were sold as "with Arduino bootloader".
In order to do the Tools > Burn Bootloader process, you need to connect an ISP programmer to the Uno that holds the new ATmega328P. If you don't own a dedicated ISP programmer, you can use a spare Arduino board as an "Arduino as ISP":
I don't have a second board, but I do have a USBASP programmer.
Using Avrdude, and the USBASP connected to the UNO, with my chip in it's socket, I burned the bootloader, then using the UNO, I programmed the 'blink' program. It's now blinking away happily.
I'm glad to hear it's working now! the USBasp is a great programmer. It's convenient to have a dedicated programmer, rather than having to wire up an Arduino as ISP.