I finally got a successful workaround for this problem.
I was facing this problem probably since emacs 24.3 and also on 24.4 and the master head builds from emacs git for version 25.0.50.0.
I was getting "*ERROR*: Invalid face: linum" when trying to start emacs with "emacsclient -a '' -c" with my init.el having "(require 'nlinum)".
Workaround:
(if (daemonp)
(add-hook 'window-setup-hook
(lambda ()
(message ">> Daemon mode")
;; It is mandatory to load linum AFTER the frames are set up
;; Else, I get "*ERROR*: Invalid face: linum"
(require 'nlinum)))
(progn
(message ">> Non daemon mode")
(require 'nlinum)))