In the past 5 years (2011-2016), your father lived in Canada from 2011-2015 as a PR. He did meet the minimum 730 days requirement, and was also granted a new PR card.
So, why did CIC think otherwise?
He didn't say he lived in Canada from 2011-2015. He met RO for 2010-2015. 2010 would have fallen off by now and can no longer be counted. Depending on the time spent in Canada from 2011 until the replacement card was ordered, he may be short of days already, despite the 2020 renewal date. It's based on the date a replacement card was applied for.
As an example: Landed January 2010, left January 2011: 365 days, Returned January 2014, applied for replacement card February 2015: 365 days plus; Total 730 days+
-Left May 2015 after new card (January 2014-May 2015): 516 days, lost card and applied for renewal 2016: the previous 5 years (2011-2016) total would be short 200ish days for RO.
That's my take on it........It's all about timing.