Hi,
As an iPhone, enabling the Messages app causes the Number to verify with the iMessages server.
Once that is done it can send iMessages from the Number (and Receive them back).
Your Mac will have listed the Mac's Apple ID used in iMessages and the iPhone Number that was linked.
That would be because the apple ID had been added to the iPhone and you had accepted the Pop ups on the Mac to confirm this link
IF you removed the first iPhone from being registered with iMessages then it will show only the Apple ID. https://selfsolve.apple.com/deregister-imessage
At this point the Mac does not know about the new Number for the new iPhone and the iPhone knows nothing about the Apple ID.
It is as Allen linked you to and you described, you have to link them like the original iPhone and the Mac were.
You may find the Mac version of Messages and the iMessages account still lists the old iPhone number in Receive At (and the Start From drop down).
This is because the com.apple.ids.service.com.apple.madrid.plist item never has old details removed.
Close the app and delete this .plist (It is in ~/Library/Preferences) and the number will be removed (it also removes the Apple ID and you need to reset and accept the pop ups about the iPhone again)
If you have Xcode (free) you can edit this file and just remove the old iPhone number.
8:54 p.m. Saturday; July 11, 2015
iMac 2.5Ghz i5 2011 (Mavericks 10.9)
G4/1GhzDual MDD (Leopard 10.5.8)
MacBookPro 2Gb (Snow Leopard 10.6.8)
Mac OS X (10.6.8),
Couple of iPhones and an iPad