Since you are getting the message that the style already exists then I would assume that you are not seeing it because the style list only shows the styles which are set to be visible.
Go to the Styles Pane and Manage Styles to see the complete list of styles including the 'hidden' ones. Read this link to help you to understand what is actually happening
http://wordfaqs.ssbarnhill.com/DisplayStyles.htm.