does archive.php contain:
<?php /*
Template Name: Archives
*/
?>
or something similar? It's the only way it will show as a template.
Then I decided to edit the title - can you clarify this - when you say you edited the title, where specifically did you edit the title?
Can you write to your htaccess? Pages tend to have issues with certain hosts and permissions.
Try this, and I may be stating the obvious, but just go through it again for clarity:
1) ensure your archives.php is correct and that the top part of the file contains the above template requirement
2) set your htaccess to 777
3) create a new page
4) can you see the archives.php file in the template selection box?
5) if no, duplicate the file, rename the template name within the PHP file to someting else like Test, and repeat the process. Does the template display?
Of course the template shoudl display regardless of whether you enter text, but I'm just speculating here.
edit: not sure if it's any help, but here's my archives.php, you can test it out?
<?php /*
Template Name: Archives
*/
?>
<?php include "header.php"; ?>
<h2>Archives by </h2><br />
<ul>
<?php wp_get_archives('type=monthly'); ?>
</ul>
<br />
<h2>Archives by Category</h2><br />
<ul>
<?php wp_list_cats(); ?>
</ul>
<br />
<?php include "footer.php"; ?>
Addtionally, ensure that there are no additional white spaces above and below the file. It may just be sods law and one of those random events.