That news story was a bit misleading. The Canes beat writer is the one who said the Canes get first priority, Rutherford was saying he'd put a claim in for Boychuk if the Pens Waived him. Later, the Canes official PR guy tweeted this (and said this information was confirmed by Rutherford). There is a whole string of tweets by him that you can check out if you want to.
Michael Smith @MSmithCanes
Re: Boychuk on waivers, #Canes don't have "first dibs"
All teams can still put in claims in, and the player is awarded to team with "worst" record.
Also, I read through the CBA. The only mention of the original team that waives a player that I could find is as follows. There is no mention of priority given to the original team.
When a Club claims a Player on Waivers, and, subsequently, in the same season it requests Waivers on the same Player and the original owning Club is the successful and only Club making a Waiver claim, then the original owning Club shall be entitled to Loan such Player to a club in another league within thirty days without further Waivers being asked; provided that such Player has not participated in ten or more NHL Games (cumulative) and remained on an NHL roster more than thirty days (cumulative) following such successful claim.
Lastly, the Canes beat writer said that the Canes were putting a claim on Boychuk as they needed him for Charlotte, but Nashville had priority due to the lower standings.
Chip Alexander @ice_chip
Hearing the Canes will claim Boychuk off waivers. Badly needed in Charlotte with injuries to Dalpe, Nodl.
Conclusion: There is no waiver priority for the team that originally waived a player. The Canes most definitely put in a claim on Boychuk, but Nashville had a worse record and was thus awarded Boychuk.