Is it ok to send an email informing about your new paper?
I think there are two important factors to keep in mind when writing unsolicited email, which could be taken as spam by the person who receives it:
Whether you believe, in good faith, that the receiver will find the information useful. That test is not as easy as it may seem, because what seems obvious to you (“this guy in field Y will be happy that we're developing somewhat related concepts in field X that may generate a new vision of his field”) may not be to him (“why is this X specialist writing to me to promote his recent work I don't care about?”). Messages need to be tailored, so that people can immediately see how your paper can be of interest to them.
The frequency of such messages: if you write 5 papers a year on a given topic, and send a nice informative email each time, that is a lot of mail! Consider doing this only once in a while, maybe for high-profile articles or reviews.
Now, regarding whether it's accepted practice (and common practice): I receive a dozen such emails of this nature per year, from colleagues in my field, and every time I am actually interested in their paper. I have not yet received spam of that sort, i.e. notification of new papers I couldn't care less about (I receive lots of spam job applications, on the other hand).
I also do it myself, once or twice a year: sit back, think about my recent papers, and ask myself “what colleagues do I have that may be interested in this and that?”. Usually, I then write a few different emails, depending on the specific interests of the colleagues in question, so that the email is personalized. I also use that occasion to ask questions to them , if I have any of relevance, asking their opinion on recent developments (by them, me or other groups) in our field.
Yes, I think this is absolutely acceptable, and indeed if you are at the beginning of your career, highly encouraged. When I was a graduate student I was shocked when my advisor asked me to e-mail my paper to most of the famous people working in the field. I was even more surprised when several of them wrote back with very substantive replies.
To make sure you're not being intrusive (which I recommend if the recipient is famous, and/or you don't know him/her personally), word your e-mail in such a way that suggests that you would welcome, but don't expect, a reply. i.e., "If you have any comments I would be grateful to hear them."
As is indicated by other answers, the practise is acceptable in general but there is a fine line when it becomes intrusive.
In addition to what has been stated already, I would add that if your paper is published in a journal that is well known to anyone in the field, the paper is less likely to come as a (pleasant) surprise. If it is published somewhere where it is less likely that many would normally find it, then the information is more likely positive.
Another factor is how you write your mail. If you send the paper to persons who do similar research you could point out the common interest from your side and use that as an "excuse" to provide a copy of your paper. It is easier to accept getting stuff if the there ios a clear reason or coupling explicitly stated in the mail.
The worst that can happen is otherwise that someone tells you not to send more material, I doubt anyone would get annoyed to the point where it may affect you negatively (unless you persists despite wishes to the contrary). Despite internet access, RSS feeds etc, I still find that I miss good papers, particularly from journals more peripheral to my subject.