If any one of you had a network storage device hooked up to a different router that gave it an IP address ranging from 100 to 149 (last 3 digits), then it is most likely that the hard disk fails (not just itself, but the internet connection completely!!) when you hook it up to your new FiOS router. This is because Verizon dedicates IP addresses from 220.127.116.11.100 to 192.168.1.149 for FiOS Televisions (which are also called as IPTVs).
So, a possible solution for network hard disk not working is to make sure that the hard disk does NOT get a IP address in the above range!!
Thanks to a Verizon associate who helped me figure out ths one! Although, you need a lot of patience before you can someone to talk to you on the phone !! 😞