I've got some functionality along this line in DBIx::SQLEngine -- feel free to copy out the relevant bits or use the module as a whole:

  my $sqldb = DBIx::SQLEngine->new( $dbh );
  print $sqldb->detect_table($tablename) ? 'Y' : 'N';
[download]

Basically I just try to select from the table and see if it succeeds; depending on which kind of database is in use, a different syntax is used to make a trivial query like "select * from $tablename limit 1" or "select * from $tablename where 1 = 0".

See the sql_detect_table() method in various "Driver::Foo" subclasses in the DBIx::SQLEngine distribution for the different queries.