Ok, I've finally solved the problem after more googling and reading.
Here is an example .spec file that one can use to build RPMs that will put a menu item into the KDE menu. It's heavily commented for your convenience.
Note that if this still doesn't work, you can always right click on the KDE menu, edit menu, then click the Save (diskette) icon and then after it's done, the icon should be in the menu. Though you shouldn't have to do this if you put it together based on this spec file as it should place the icon in the menu and update it automatically.
Also this assumes that you are creating a $HOME/rpm directory with the appropriate BUILD, SOURCE, SPEC, etc. directories. In the BUILD directory, create a subdirectory for your application. Make sure it's the same as the application name. as that is what it uses here.
Code:
# DEFAULT.SPEC
# RPM Spec file for Mandriva 2006 and KDE 3.4.2
# By Fuzzie Dice <fuzziedice6000@yahoo.com>
#
# Example RPM Spec File for installing applications into Mandriva 2006 with KDE
# This will also create the necessary menu items so that users can immediately
# see the menu item.
# IMPORTANT: Be sure to edit this file and save it as YOUR_APP.spec before you use it!
# Areas to add items are in ALL_CAPITAL_LETTERS
# Headers: Note that if you're doing this for a different architecture,
# Specify it in the %define _target_cpu YOUR_ARCH
%define name YOUR_APP_NAME
%define version APP_VERSION
%define release 1mdk
%define _target_cpu i586
# Information about the application
# NOTE: Change the License if different from GPL
Name: %{name}
Version: %{version}
Release: %{release}
Summary: SHORT_DESCRIPTION_OF_YOUR_APPLICATION
Source: URL_WHERE_PEOPLE_CAN_GET_SOURCE_FILES
URL: URL_OF_APPLICATION_WEB_SITE
Group: RPM_DATABASE_GROUP_TO_PLACE_ENTRY_IN
BuildRoot: %{_topdir}/BUILD/%{name}
License: GPL
# This optional line will make sure certain dependencies are met.
# Use >= to be sure that the item is at least the specified version or later.
# Requires: qt4-common >= 4.0.1
%description
PUT_APPLICATION_LONG_DESCRIPTION_HERE
# This area sets up the KDE Menu system and will update the menu
# during installation or uninstallation.
%install
cat << EOF > $RPM_BUILD_ROOT%{_menudir}/%{name}
?package(%{name}): needs=x11 icon="ABSOLUTE_PATH_TO_ICON_FOR_MENU" section="SECTION_PATH_SUCH_AS Multimedia/Graphics" title=YOUR_APP_NAME longtitle="LONG_MENU_DESCRIPTION" command="ABSOLUTE_PATH_TO_APP_EXECUTABLE"
EOF
cat << EOF > $RPM_BUILD_ROOT%{_datadir}/applications/%{name}.desktop
[Desktop Entry]
Encoding=UTF-8
Type=Application
Exec=ABSOLUTE_PATH_TO_APP_EXECUTABLE_AND_ANY_COMMAND_LINE_OPTIONS
Icon=ABSOLUTE_PATH_TO_ICON_FOR_MENU
Terminal=false
Name=YOUR_APP_NAME
Comment=APP_SHORT_DESCRIPTION
# Adjust this line to place in whatever menu category appropriate.
# This may be different from the 'section' above.
Categories=Application;Graphics;
EOF
# Update KDE menu so user can see icon immediately after installing
%post
update-menus
# Update KDE menu so icon is removed immediately after uninstalling
%postun
update-menus
# These are the files that will be installed into the system
# Note that you should have all of the directory structure in your
# RPM BUILD directory. This includes any that will create the above
# files, such as /usr/lib/menu and /usr/share/applications.
# Create the directories yourself even if you don't put anything in
# them yourself. This spec file needs them to be at least present.
%files
%defattr(-,root,root,0755)
%dir /usr
/usr/*
# This is a changelog which is to be updated whenever you make changes
# to the RPM Build.
%changelog
* DAY MON DD YYYY YOUR_NAME <YOUR_EMAIL_ADDRESS> PROGRAM_VERSION-1mdk
- Change #1
- Change #2
- Change #3
- etc.
Hope this helps others who may have run into this problem. Took me an all-night stint and most of today on the computer plus a lot of googling and trial and error to get this to work.