Step by step, pretty easy:
1. Download SQLite Database Browser (works with all OS')
2. Pull the following file off your phone (easiest way is using adb): /data/data/com.htc.provider.weather/files/WP_0409WWE.db
3. Open the db file in SQLite Browser.
4. Click on the "Browse Data" tab.
5. Next to "Table:" choose "locationlist"
6. Click on "New Record" on the top right, it should automatically create a blank one at the end of the list.
7. Double-click on the empty box under "code" and enter text in this format: NAM|US|<state>|<city> So, for example, NAM|US|NY|NEW YORK CITY (no spaces or line breaks after the block of text (you can have spaces in the city name))
8. Under "name", put the desired city name, such as "New York City" without any spaces or line breaks after the block of text.
9. Under "state", put the state name, such as "NY" in the same format as "name"
10. Under "timezone", put either 300, 360, 420, or 480 in, depending on what your timezone is:
Eastern time - 300
Central time - 360
Mountain time - 420
Pacific time - 480
11. Under "timezoneld", put either "America/New_York", "America/Chicago", "America/Denver", or "America/Los_Angeles" in, again, depending on the timezone you live in:
Eastern time - America/New_York
Central time - America/Chicago
Mountain time - America/Denver
Pacific time - America/Los_Angeles
That's it! Save it, push it back to /data/data/com.htc.provider.weather/files then reboot and you should be able to search for your town!
Special thanks to the guys who figured this out first (I don't remember your names, but thank you! :P)