Security of N bit HMAC

Lets say that I am using 128 bit HMAC. How many operations are needed to find a "non secure" message. Is a birthday attack possible?

The short answer is: $2^{128}$ operations, no known birthday-like attack.
The original proof claimed that if the compression function is a PRF (i.e. the choice of a block value "selects" the compression function as if randomly among functions which take the state as input and produce the corresponding output) and the hash function is collision-resistant (in a "weak" way; it needs not be resistant to all kinds of collisions) then HMAC is secure. That proof worked up to $2^{n/2}$ invocations of the compression function (for a hash function with a $n$-bit output). Later on, Bellare published a new security proof which removes the condition on weak collision resistance, and enhances proven security up to $2^{n}$ .
Now the fine print: the security proof works only as long as the PRF assumption holds. However, if the PRF assumption holds, then the hash function which uses that compression function in the MD construction is necessarily resistant to collisions up to $2^{n/2}$. Therefore, if a MD-like hash function is proven not to be collision resistant up to $2^{n/2}$, then this implies that its underlying compression function is not as PRF as it should. This is true, in particular, for MD4, MD5, SHA-0 and SHA-1. For these functions, the PRF assumption cannot be held, hence the HMAC security proof is not applicable to HMAC/MD4, HMAC/MD5, HMAC/SHA-0 and HMAC/SHA-1. This does not mean that we know a way to turn collision attacks into attacks on HMAC. Indeed there is no known attack faster than $2^{128}$ on HMAC/MD5. However, there is a known forgery attack on HMAC/MD4. Note that this attack has cost $2^{58}$, which is quite a lot (and explains why the attack was never actually demonstrated), whereas resistance of MD4 to collisions is, by itself, zero (generating the collision takes less time than simply hashing the two messages to verify that it works).