I am assuming that the 'art-boxes' contains thumbnailed versions of the random backgrounds? When the page loads, choose a random background, and hide it from the list of other backgrounds? A kind of reverse gallery selection?

Again I'm with @jamy_za and although I understand your script, if it was written in jQuery it would seem to read more semantically.

artcontainer.style.display = 'none';
// vs
$('#artcontainer').hide();

I also find it easier to draft out ideas - even if the script itself is not valid (I would have at least broken the procedure down!):

$('#header').css('background-image', picture-url); //'picture-url' being the result of the math;
	 $('#artcontainer a[href="'+ picture-url'"]).hide(); //Find the link to the same image, and hide it;

The code hasn't been tested, so may not work - but even then you can see the method I was aiming for?

Brain was definitely fried last night, here's the link to the cleaned down version
http://emasai.com/depinho/jstrial.html

So you want to rearrange the a elements randomly ?

well with jquery try:

 $(document).ready(function(){
	 var rows = 3;
	 var cols = 4;
	 var arr = new Array();
	 function get_class() {
		var r = Math.ceil(Math.random()* rows); 
		var c = Math.ceil(Math.random()* cols);
		var cssclass = 'row'+r+'-'+c;
		if($.inArray(cssclass, arr) < 0){
			arr.push(cssclass);
			return cssclass;
		} else {
			return get_class();
		}
	 }
	 $('#art-boxes a').each(function(i,e){
                        $(this).removeClass($(this).attr('class').match(/row\d-\d/gi));
		 	$(this).addClass(get_class());
		 });
	 });

I havn't testet it, so don't blame me ^^

Ok thats easy ^^

<script type="text/javascript">
	
window.onload = function () {
	var header = document.getElementById('header');
    	var pictures = new Array('images/image1.jpg','images/image2.jpg','images/image3.jpg','images/image4.jpg','images/image5.jpg','art-boxes');
    	var numPics = pictures.length;
    if (document.images) {
        var chosenPic = pictures[Math.random() * numPics];
	 		
	 if(chosenPic == 'art-boxes'){
	     document.getElementById(chosenPic).style.display = 'block';
	 }else{
	     header.style.background = 'url(' + chosenPic + ')';
         }
    }
 }
</script>

and html

<div id="contentright">
    
    <div id="artcontainer">
        <div id="art-boxes" style="display:none;">
        <a class="row1-1" href="#"></a>
        <a class="row1-2" href="#"></a>
        <a class="row1-3" href="#"></a>
        <a class="row1-4 norightmargin" href="#"></a>
    
        <a class="row2-1" href="#"></a>
        <a class="row2-2" href="#"></a>
        <a class="row2-3" href="#"></a>
        <a class="row2-4 norightmargin" href="#"></a>
    
        <a class="row3-1" href="#"></a>
        <a class="row3-2" href="#"></a>
        <a class="row3-3" href="#"></a>
        <a class="row3-4 norightmargin" href="#"></a>
        </div><!-- END ARTBOXES -->
     </div><!-- END ARTCONTAINER -->   
        
        </div><!--END CONTENTRIGHT-->

Hope thats want you want ;)

So, you want the five background images to alternate in front of the boxes, while this happens the boxes will not be visible. Then, after the five images, the boxes show up. Is that right? Now, if you want the background images to show in front of the boxes you will have to actually put them as an image in front of the boxes with absolute positioning and a higher z-index(all this with css). then have a function change the image in front of the boxes in an interval that you specify like setInterval(). Also, when the function runs through all the images, just place an empty source and nothing will show up, therefore leting the person see the blocks... Sorry if it doesn't make sense, but I wrote this in a real big rush.. Hope this helps...

Well i should read it twice after writing code without testing it or: copy/pasting is bad :P
There is no element with the id of 'header' in your dom..
Change also:

var header = document.getElementById('contentright');