Does your Record.pm file have a package Record; declaration? If not, the file will be loaded and compiled by the use command, but no Record namespace will be created.

BTW, it's probably a good idea, from a stylistic standpoint, to prefix your classnames with something so they don't conflict with other stuff. "Record" is pretty vague. Perhaps something like YourProject::FooRecord, where 'foo' is the type of thing the record is about, would be more descriptive.

Finally, make sure everything compiles correctly under use strict, or you're begging for pain.