Can we get a patent for a cloud service?

It really depends on the nature of the technology. If the only thing that differentiates it from existing descriptions of the technology (or competitive products) is the fact that it is a cloud service, it is unlikely. The implementation platform of the technology is mostly irrelevant to its patentability. Ever since the Alice v. CLS Bank ruling last year by the Supreme Court, the patent office has gotten much more strict on software patents and business method patents, so that is the source of the negativity you have heard about software patents. However, if you have an innovative system that really does something that was not done before, then the fact that it uses a cloud implementation doesn't present any kind of special problem. I'd have to know a little bit more about what you are doing to give a more complete answer.