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.

I concur with Allan. The Alice v CLS Bank decision changed patent law quite a bit regarding software patents but it is not correct that software-based technologies cannot be patented; we just need to be much more particular about them now. The key point to keep in mind is that in order to be patentable your invention needs to have some aspect that is both new and not obvious from what was known before. If your invention uses cloud computing to conduct the same personal health monitoring process as was done in the past then without more detail it sounds to be obvious and not patentable. If there's something else that's different that something else may give you a reasonable basis for actually getting a patent granted.
Alternatives to patenting generally offer less protection: software is subject to copyright protection but that's narrow and often can be easily designed around. It protects you if someone actually copies your code, but there are open source license issues that come into play if you used some open source code when writing your program.