I'm RDP-ing to a WIN2K8 machine from Ubuntu 12.04+Remmina but EVERY TIME I'm prompted with a Certificate Validation.
Does anybody knows how to avoid these messages or validate them for good?
Neither of these options will prompt you ever :)
You get this message because the hostname of the certificate does not match the hostname configured in the connection profile in Remmina. To avoid the certificate validation message you can put the fingerprint of the server-certificate in ~/.freerdp/known_hosts.