Apparently it was removed from Ovi Store by Nokia because of these problems. Too bad they didn't also remove it from the repository which would have made a lot more sense...

Hopefully they get these problems sorted out soon and Angry Birds back in the store.

Edit: Actually the package was also removed from the repository but the change just takes some time to propagate to all load balancing servers.