There seems to be some problem with the portage provider. Here's what I have installed (output of eix -e mysql):
[I] dev-db/mysql
Available versions: [M]*3.23.58-r1 4.0.27-r1 4.1.22-r1 [M]~4.1.23_alpha20070101-r61 [m]5.0.26-r2 [m]~5.0.32 [m]~5.0.34 [m]5.0.38 [m]5.0.40 [m]5.0.42 {berkdb big-tables cluster debug embedded extraengine innodb latin1 max-idx-128 minimal perl raid readline selinux ssl static tcpd}
Installed versions: 4.1.22-r1(14:16:44 07/09/07)(berkdb -big-tables -cluster -debug -embedded -extraengine -latin1 minimal perl -raid -selinux ssl -static)
Homepage: http://www.mysql.com/
Description: A fast, multi-threaded, multi-user SQL database server.
So I have the latest stable version, 4.1.22-r1 installed - puppet thinks I only have 4.1:
notice: //base/foo.bar.hu/mysql/Package[mysql]/ensure: ensure changed '4.1' to '4.1.22-r1'
The other packages doesn't seem to have any problem and I only have this bug with puppet 0.23.0, not with 0.22.4.