one of our server has returned a icmp time stamp response such that the scanner (nmap) is able to guess the uptime of the server. Does this constitute a real threat and should I be concerned?
It is an informational threat. It allows an attacker to gather information that may be useful in determining what other attacks might work. For example, if nmap can tell me that it looks like a Centos OS and it has an uptime of 60 days, then I I know that any kernel security update packages released in the last two months have not been installed and activated. As a result, I may be able to determine which attacks against that system are likely to work.
For an internal server, you should only be mildly concerned. For an Internet facing server, you should be slightly more concerned, and should limit ICMP access to that server as a matter of best practices. But this is not a major concern in either scenario.
In any case, if the OS vendor has a patch or a configuration workaround, you should apply it - no reason not to, and it might even help.
For a minor issue like this, the largest concern is usually placating your auditor. If this is the biggest thing they find, you're doing well!