Hi timsig,
I had this problem a short while ago and was pulling my hair out. It does this because you have a page that already uses that Permalink. If you have recently trashed a page that would have used the same permalink, go in to your trash and permanently delete the page, then try and edit the permalink again. It should now work. The reason for this is that when a page is deleted, it still resides in the database, meaning the permalink is still technically in use until it is removed from the database.
Hope this solves your problem.