Well.. not totally iBrick, but just God awfully slow, especially Messages and Settings apps. Googling showed that iPhone 3G pwners have had issues with slow app startup since 2.x times. Few of them blamed Cydia.app, others indicate that restoring a pwned 3.0 phone from 2.x backup is a way to troubles. I am leaning towards the latter.

What ever was the reason, I chose to restore my PwnageTool’ed iPhone to factory defaults, set it up as a new device and then use redsn0w to jailbreak it again. The tutorial is here.

Beginning with the fact that redsn0w jailbreaking was faster (custom firmware creation not required), it even preserved my Springboard layout and I did not have to resync my data to the device. Two thumbs up for redsn0w.
And so far the phone seems to operate normally again.

Do not try this at home:
I deviated from the forementioned redsn0w tutorial in the way that I chose to install Icy instead of Cydia. This proved to be a mistake, as Icy is reportedly not working currently on OS 3.0 jailbreak. For me it resulted with error #1 for some packages (only some, as I could install BossPrefs, and Cydia for example, unfortunately Cydia refused to start up afterwards).

EDIT: I originally just re-redsn0wed my iphone with Cydia selected, hoping it would sort out the issues, but as the APT database was reset all the stuff already installed was orphaned.
I wanted a clean start and so I restored to defaults (again) and jailbroke the vanilla device. (Note: this was totally my fault and does not diminish the value of redsn0w).

After resyncing all data from the Mac I have a working device again.