What I have observed is that many newbies come with phrases based on
nouns like "My love for you is strong" and then we suggest them to
rephrase it like "I love you very much".

Sure, this is a case where we have a verb muSHa' love and no corresponding noun, and so naturally one will turn to the verb. And sometimes it's true that we have a verb with no corresponding noun. I don't think this makes Klingon verb-centric; it just means Klingon doesn't noun its verbs and verb its nouns as often as English does. The balance of Klingon is different than that of English.

And then I recently started to wonder why we do that. Is it really the
case that there are more verb-centric expressions or constructions than
nouns? Or did we really just make that up many years ago, when we were
missing so many words?

I think missing words was part of it. I think fear of and confusion about -ghach was another. I think the fact that many English nouns get translated into Klingon verbs is significant and should be noted for the student, but I don't think that the entire character of the language should be named based on just that.

It's really just an admonition to the student not to translate word for word. Find out how Klingon wants to construct things and expression your idea using those Klingon tools. Sometimes, what is a noun in English is necessarily a verb in Klingon. But don't overstate this.

-- 
SuStel
http://trimboli.name