Ok, Finally got it. Thanks for pointing me in the right direction.
I was putting the rewrite in the <virtualhost> of the newdomain.company.com
It needs to be in the olddomain.company.com's virtualhost section.
That makes sense, but I just didn't think of it.
Code:
<VirtualHost 999.999.999.999:80>
ServerAdmin webmaster@olddomain.company.com
DocumentRoot /www/html/oldcompany
ServerName olddomain.company.com
ServerAlias www.olddomain.company.com
ErrorLog logs/olddomain
<Directory /www/html/oldcompany>
AllowOverride All
Options ExecCGI Includes FollowSymlinks +Indexes
Order allow,deny
Allow from all
RewriteEngine on
RewriteCond %{HTTP_HOST} ^www.olddomain.company.com
RewriteCond %{REQUEST_URI} ^/~(.+)
RewriteRule (.*) http://newdomain.company.com/~%1 [L,R=301]
</Directory>