don't see the issue yet, but here's a crack at refactoring to simplify it some, which hopefully will lead you in the right direction..

recurQuery(0,0);

my $cat_sth = $dbh->prepare("SELECT id, parentid, catname from categor
+ies WHERE parentid = ?");

sub recurQuery {
  my ($parentId, $level) = @_;
  $cat_sth->execute($parentId) or die $dbh->errstr;
  while (my $data = $cat_sth->fetchrow_hashref) {
    printf qq{ <option name="%s">%s%s</option>\n },
      $data->{catname},
      '&nbsp;*' x $level,
      $data->{catname},
      ;
    recurQuery( $data->{id}, $level+1 );
  }
}
[download]

Some notes:

• prepare the statement once
• use placeholders
• the query only needs to be in the function once -- recursion does the rest; don't need to pre-test for rows .. the while loop just won't happen in the next level if there aren't any more children
• the x operator can replace the for loop for the indenting
• printf for cleaner output (also consider separating logic/presentation even further by having the recurQuery return an array, and loop over that to display later)
• fetch hashref's instead of rows -- much easier to read a key name than just an array index

You should put in some protection for infinite recursion, too.