After a week of going back and forth, cursing at my computer and trying to find out why on earth this OPENID plugin was not working I finally found the why today, actually a few minutes ago.
I tried deactivating all the plugins I had installed just to make sure it was not a incompatibility issue, but that was not the case, the problem was actually with SSL. I have FORCE_SSL_ADMIN in my configuration file set to true. While trying to leave comments with my openID on other blogs I was seeing a huge URL on the browser every time the comment posting failed and noticed some https, so I changed the true value of the SSL to false in the configuration file and the openID plugin finally works. I was able to leave a comment on a friends blog just a couple minutes ago.
I don't know if all the people that have been having problems with the openID plugin uses SSL for their admin area, but in case you guys do, try to disable SSL for admin and see if that makes a difference.
Cheers!