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

I am still having the same issue. I've uninstalled, reinstalled multiple times. Mine cannot create backup shares larger than 250 GB. If I choose a smaller backup to create, it creates it but the backup disc will not start. Any ideas?

The Time Machine support is a bit flaky, but do you actually have . 250Gb contiguous free space on one of your WHS hds? it may be you have insufficient space

Check this thread if you haven't.
viewtopic.php?f=19&t=5997

_________________
Alex Kuretz
Remote Notification: Monitoring and alerting for your Home Server via email, Twitter, text message, RSS, push notifications, and on your Mac desktop
Have you tried our Add-Ins? If so, be sure to Rate them at WeGotServed.