If you purchased it from an online site other than Samsung (or if the listing did not specify OEM), it's likely a counterfeit without Bluetooth circuits in it. Purchase only known original Samsung S Pens to ensure compatibility.
Put the replacement S Pen into the phone, then go to the following:
Settings | Advanced features | S Pen | 3 Dot menu in the upper right | Reset S Pen
This will take a moment, but when it is done, you should have all of the original S Pen features, unless your S Pen is not official as The_Chief states.
