I'm using Apache2 on Ubuntu Lucid Lynx. I have config set to use .htaccess like normal. This is my default site:

<VirtualHost *:80>
        ServerAdmin webmaster@localhost

        DocumentRoot /var/www
        <Directory />
                Options FollowSymLinks
                AllowOverride All
        </Directory>
        <Directory /var/www/>
                Options Indexes FollowSymLinks MultiViews
                AllowOverride All
                Order allow,deny
                allow from all
        </Directory>

        ScriptAlias /cgi-bin/ /usr/lib/cgi-bin/
        <Directory "/usr/lib/cgi-bin">
                AllowOverride All
                Options +ExecCGI -MultiViews +SymLinksIfOwnerMatch
                Order allow,deny
                Allow from all
        </Directory>

        ErrorLog /var/log/apache2/error.log

        # Possible values include: debug, info, notice, warn, error, crit,
        # alert, emerg.
        LogLevel warn

        CustomLog /var/log/apache2/access.log combined

    Alias /doc/ "/usr/share/doc/"
    <Directory "/usr/share/doc/">
        Options Indexes MultiViews FollowSymLinks
        AllowOverride None
        Order deny,allow
        Deny from all
        Allow from 127.0.0.0/255.0.0.0 ::1/128
    </Directory>

</VirtualHost>

I've tried lower case "all" (AllowOverride all) as well.

My .htaccess file looks like this:

//Rewrite all requests to www
Options +FollowSymLinks
RewriteEngine on
RewriteCond %{HTTP_HOST} ^mydomain.com [nc]
RewriteRule ^(.*)$ http://www.mydomain.com/$1 [r=301,nc]

//301 Redirect "old_junk.html" File to "new_junk.html"
Redirect 301 /old_junk.html /new_junk.html

//301 Redirect Entire Directory "old_junk/" to "new_junk/"
RedirectMatch 301 /old_junk/(.*) /new_junk//$1

// Copy and paste redirect examples from above:

(with mydomain replaced with my actual domain... and my computer is plugged in)