Do a Spotlight search using the name of your bookmark as your search term. Maybe Safari is saving it into a bookmark folder and you're just not seeing where it's being saved. I'm always being trigger-happy and dropping bookmarks into a sub-folder prematurely!
If you still can't find the bookmark, go through the basic troubleshooting steps first. After each step, try bookmarking a page to see if your problem is resolved.
1) Quit/relaunch Safari
2) Log Out/ Log In of your user account
3) restart your Mac
If THAT doesn't help....
1) Open a Finder window and navigate to ~/Library/Safari (where ~ is your username)
2) Right-click on "bookmarks.plist" and click "Get Info" to bring up the inspector
3) Under "General", make sure that the "locked" box is UNchecked.