301 Redirect

[#1]

I want to redirect a page which has been deleted and now gives 404 to a new page on the same site.
Have entered the following format into an htaccess file and uploaded to the root.
Redirect  301 /olddirectory/oldfile.html http://mysite.co.uk/newdirectory/newfile.html
However it does not work.
Only other instruction in the htaccess file is the error not found file which works ok.
I think this is a relatively simple problem but can't find the answer.
Help would be appreciated.
Thanks

[#2]

Just checked my own Redirect 301 and am guessing you might need to use http://www.mysite rather than just http://mysite. The other not so obvious problem could be the that either file is incorrectly named as the names are case sensitive.

[#3]

Hi there,
Is the request you are rewriting correct, i.e. the path has to start from the root of your website, usually your htdocs directory.
e.g.
If I have the following structure:

htdocs/
htdocs/index.html
htdocs/stuff
htdocs/stuff/.htaccess
htdocs/stuff/index.html

If I want to redirect www.mysite.com/stuff/someotherstuff.html to google using htdocs/stuff/.htaccess I'd need to put something like:

Redirect 301 /stuff/someotherstuff.html http://google.com/

and NOT

Redirect 301 someotherstuff.html http://google.com/

See what I mean?
HTH