Use Thread::Queue::Any
instead of Thread::Queue
I ran into the same problem trying to pass references to queues.

A queue, as implemented by Thread::Queue::Any is a thread-safe data structure that inherits from Thread::Queue. But unlike the standard Thread::Queue, you can pass (a reference to) any data structure to the queue. Apart from the fact that the parameters to enqueue are considered to be a set that needs to be enqueued together and that dequeue returns all of the parameters that were enqueued together, this module is a drop-in replacement for Thread::Queue in every other aspect. Any number of threads can safely add elements to the end of the list, or remove elements from the head of the list. (Queues don't permit adding or removing elements from the middle of the list).
From: Perl Documentation Thread::Queue::Any

Also look at some of the nodes liz has done on the subject of threads in general.

I don't have 5.8.2 but the example you are refering to if it is this

  use Thread qw(async); 
    use Thread::Queue;

    my $DataQueue = new Thread::Queue; 
    $thr = async { 
        while ($DataElement = $DataQueue->dequeue) { 
            print "Popped $DataElement off the queue\n";
        } 
    }; 

    $DataQueue->enqueue(12); 
    $DataQueue->enqueue("A", "B", "C"); 
    $DataQueue->enqueue(\$thr); 
    sleep 10; 
    $DataQueue->enqueue(undef);
[download]

is different because it is using Thread not threads.

Update Hmm I see it in perltut both ways for 5.8.0
here:
Using threads
and
here:
Using Thread

Updated Update I think looking at the functions in Thread::Queue and threads::shared this paragraph may explain what is happening:

share VARIABLE share takes a value and marks it as shared. You can share a scalar, array, hash, scalar ref, array ref or hash ref. share will return the shared rvalue. share will traverse up references exactly one level. share(\$a) is equivalent to share($a), while share(\\$a) is not. A variable can also be marked as shared at compile time by using the shared attribute: my $var : shared. If you want to share a newly created reference unfortunately you need to use &share([]) and &share({}) syntax due to problems with Perl's prototyping.
From :threads::shared

The Source of Thread::Queue - without the POD

package Thread::Queue;

use threads::shared;
use strict;

our $VERSION = '2.00';


sub new {
    my $class = shift;
    my @q : shared = @_;
    return bless \@q, $class;
}

sub dequeue  {
    my $q = shift;
    lock(@$q);
    cond_wait @$q until @$q;
    cond_signal @$q if @$q > 1;
    return shift @$q;
}

sub dequeue_nb {
    my $q = shift;
    lock(@$q);
    return shift @$q;
}

sub enqueue {
    my $q = shift;
    lock(@$q);
    push @$q, @_  and cond_signal @$q;
}

sub pending  {
    my $q = shift;
    lock(@$q);
    return scalar(@$q);
}

1;
[download]

Updated Updated Update: This link seems to explain it best.