Not sure if you were able to get this resolved but I was having the same issues, so I'll post anyway. Just bought the EX 495.
I reinstalled the software on my mac.
I created a folder called "Backup" on my mac share.
I navigated to the HP MediaSmart Server preferences, Authenticated just fine.
I navigated to Backup tab and it gave a backup size, and clicked on the system preferences wheel just to the right of the letters "GB" and selected create.
I watched the status go from "Not Available" to "Started" which created a share that TimeMachine could see called "Backup to HP MediaSmart Server."
I opened Time Machine Preferences from the button and selected the new share "Backup to HP MediaSmart Server" Backing up without issues.
This is probably no longer an issue, but I somehow had the same issues. Fixed
System Version: Mac OS X 10.6.6
Kernel Version: Darwin 10.6.0
Model Name: MacBook Pro
Model Identifier: MacBookPro1,1
Processor Name: Intel Core Duo
Processor Speed: 2.16 GHz
Number Of Processors: 1
Total Number Of Cores: 2
L2 Cache: 2 MB
Memory: 2 GB
Bus Speed: 667 MHz